Search code examples
algorithmtime-complexitycode-complexity

Algorithm Complexity-Nested For Loops

for(j=n; j>1; j/=2)
  ++p;
for(k=1; k<p; k*=2)
    ++q;

On the first code sample, p variable belong to 1st loop. So,even they are not nested loop,will 2nd return log(n),too? I mean totally, O(loglog(n))? 

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

And these one, they are nested but k variable belong to 2nd loop. So, should it similar to 1st one? Like O(n^2.log(n)) or O(n.log^2(n))?

Solution

    1. Algorithm: First loop takes log(n) time. Second loop takes log(log(n)) time. So you have log(n) + log(log(n)). But first loop counts more. So it's O(log(n)).

    2. Algorithm: At first look what runtime you have when you only analyse the two outer for loops (means n log(n)). But unfortunately there comes an inner third for loop which makes it more complex.

      The third for loop counts from 0 to 2^m where m=log(n). So you have to sum 2^m from 0 to log(n)-1 which is n-1. So n-1 is the run time of the two inner for loops. Now you have to multiply it by the linear run time of the outer for loop. So it's (n-1)n which is n²-n. So you have O(n²) for the three loops.