Complexity of an algorithm with nested loop changing each time

Question

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

OmG · Accepted Answer · 2019-10-22 16:15:46Z

3

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.

answered Oct 22, 2019 at 16:15

OmG

19k13 gold badges69 silver badges96 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Complexity of an algorithm with nested loop changing each time

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related