CODEWITHSUNDEEP
ctime-complexity
Giorgio M.
Giorgio M.

Reputation: 81

Is the time complexity of this code correct?

Calculate the time complexity of this code fragment if the function "process" has a complexity of O(logn)

void funct (int a[], int n)
{
    int i=0
      while (i < n){
         process (a, n);
         if (a[i]%2 == 0)
           i = i*2+1;
         else
           i = i+1;
  }

I tried to calculate the best and worst case for time complexity;

Worst case is when the "else" statement get called so it should just be:

Worst case : T(n) = O(nlogn)

I have some problems with the best case. I tried this way but i don't know if this is correct

Since in the "if" statement "i" get incremented by "2i+1" it should be

i=2^k-1
2^k < n+1 

so k < log_2(n+1)

Is correct to say that the while loop get executed (log_2(n+1)-2)/2 times because this is the last possible value for which i < n ?

if so the time complexity is O(lognlogn) in best case?

Upvotes: 2

Views: 115

Answers (1)

Tom Karzes
Tom Karzes

Reputation: 24052

The best case is if the sampled values in a are all even. In that case, the complexity is O(log(n)*log(n)), since the loop trip count is O(log(n)).

The worst case is if the sampled values in a are all odd. In that case, the complexity is O(n*log(n)), since the loop trip count is O(n).

Upvotes: 1

Related Questions