Find an upper and lower bound of following code

问题:

I need to find a closest upper and lower bound of following code. I am beeginer in this so sorry for my mistake.

Upper bound for p() is O(log(n)), and lower bound is O(1)

Upper bound for notp() is O(log(n)), and lower bound is O(1)

I think that lower bound is O(1) because if I have n=4 then I get in the loop and since n%i==0 I call p() and it notice that is not a prime number so O(1) then since i=2 the other notp would not be executed. That is bast case scenario.

Worst case scenario that I go through loop so that log(n), and execute a p and a upper bound is O(log(n)) so it is O(log(n)^2) but I am not so sure that this is good, please tell me where I made a mistake?

int i;
for (i = 2; i*i <= n; i++) {
  if (n % i == 0) {
    p();
    break;
  }
}
if(i*i > n)
  notp();

回答1:

For order calculations, you would normally multiply them together when there is a loop.

for( i = 0; i < n ; i++ ){
     DoSomething(i);
}

That would be O(n), as the loop is a single case.

A nested loop would be

for( i = 0; i < n ; i++ ){ 
    for( j =0; j < n; j++ ){
       DoSomething(i,j);
    }
}

That becomes O( n^2 ) as they are additive.

If you have non-nested loops...

for( i = 0; i < n ; i++ ){
     DoSomething(i);
}


for( j = 0; j < sqrt(n) ; j++ ){
     DoSomething(j);
}

Then the O( x ), is the largest term. That is because for very large n, the smaller values of x don't matter.

So you have a loop in your case, which is O( sqrt( n ) ). That is because it is limited by i *i being less than n.

Then either one of p() or notp() will be called.

(I think p() and notp() are the wrong way round).

Re-factoring your code....

int i;
for (i = 2; i*i <= n; i++) {
  if (n % i == 0) {
    /* p(); */
    break;
  }
}
if(i*i > n)
  notp();
else
  p();

So we have the O( sqrt(n) ) time plus either of the p / notp functions which are O( log(n) )

O( sqrt(n ) + log(n) )

As the sqrt grows faster than n, it overpowers the log(n) wikipedia Big O, leaving it as the final value.

O( sqrt(n) )

回答2:

As the termination condition of the loop is i*i <= n, the most possible number of iteration of the loop is sqrt(n). As there is a break in the condition of n % i == 0, the worst case of this part is sqrt(n) + log(n) which is O(sqrt(n)). Also, eighter the second condition is true or not, as the worst case of nopt() is O(log(n)), the worst case of the algorithm in total is O(sqrt(n)).