CODEWITHSUNDEEP
algorithmtime-complexitynested-loops
Alexis Pister
Alexis Pister

Reputation: 499

Complexity of an algorithm with nested loop changing each time

I have to tell the complexity of the both following algorithm :

for ( i=1; i < n; i *= 2 ) {
  for ( j = n; j > 0; j /= 2 ) {
    for ( k = j; k < n; k += 2 ) {
      sum += (i + j * k );
    }
  }
}

for( int i = n; i > 0; i-- ) {
  for( int j = 1; j < n; j *= 2 ) {
    for( int k = 0; k < j; k++ ) {
       ... // some operation
    }
  }
}

In the first example, I know the complexity of the outer and middle loops are log(n), but I don't know how to compute the complexity for the inner one as the initialization of k change at iteration

For the second one, apparently the complexity is n^2 but I really don't understand why

Upvotes: 1

Views: 308

Answers (1)

OmG
OmG

Reputation: 18838

As you said, the outer loop is log(n) and its parameter i is not used in inner loops. For the other two inner loops:

 value of j    iteration number of the most inner loop
 j = n;        k: 0 
 j = n/2;      k: (n - n/2)/2
 j = n/4;      k: (n-n/4)/2

Hence, the sum is ((1-1/2) + (1-1/4) + (1-1/8) + ... + (1-1/2^log(n)))n/2 = (log(n) - c) * n/2 = Theta(n log(n)). Therefore, the total complexity is n (log(n))^2.

Upvotes: 3

Related Questions