-1

Hi I'm trying to analyze the time complexity of this algorithm but I'm having difficult unraveling and counting how many times the final loop will execute. I realize that the first loop is log(n) but after that I can't seem to get to a sum which evaluates well. Here is the algorithm:

for(int i = 1; i <= n; i = 2*i){
    for(int j = 1; j <= i; j = 2*j){
        for(int k = 0; k <= j; k++){
            // Some elementary operation here.
        }
    }
}

I cannot figure out how many times the loop k executes in general w.r.t to n

Thanks for any help!

IRSAgent
  • 319
  • 1
  • 3
  • 12
  • Possible duplicate of [How to find time complexity of an algorithm](http://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) –  Apr 26 '16 at 11:32

1 Answers1

5

It is O(n).

1 + 2 + 4 + ... + 2^N == 2^(N + 1) - 1.

The last loop, for a specific j, executes j times.

And for a specific i, the inner 2 loops execute 1 + 2 + 4 + ... + i times, which is equal to about 2 * i.

So the total execution times is 1 * 2 + 2 * 2 + 4 * 2 + ... + N * 2, which is about 4 * N.

Ke Yang
  • 218
  • 1
  • 6