1
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))?

  • Possible duplicate of [How to find time complexity of an algorithm](http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – Paul Hankin Apr 06 '17 at 15:32

1 Answers1

3

  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.

Community
  • 1
  • 1
gartenkralle
  • 646
  • 1
  • 11
  • 21
  • Thank you. Now i understand that return value and runtime's difference for 1st quesstion. –  Apr 06 '17 at 14:30