Why is this algorithm O(nlogn)?

Question

I'm reading a book on algorithm analysis and have found an algorithm which I don't know how to get the time complexity of, although the book says that it is O(nlogn).

Here is the algorithm:

sum1=0; 
for(k=1; k<=n; k*=2) 
  for(j=1; j<=n; j++) 
    sum1++;

Answer 1

Perhaps the easiest way to convince yourself of the O(n*lgn) running time is to run the algorithm on a sheet of paper. Consider what happens when n is 64. Then the outer loop variable k would take the following values:

1 2 4 8 16 32 64

The log_2(64) is 6, which is the number of terms above plus one. You can continue this line of reasoning to conclude that the outer loop will take O(lgn) running time.

The inner loop, which is completely independent of the outer loop, is O(n). Multiplying these two terms together yields O(lgn*n).