3

We've received a fragment of code to find its big-O:

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++)
             //do something elementary

The first line should be O(log(n)) but it gets complicated by the second line and even more so by the third. I initially thought that the second line could also be O(logn) but the upper limit j < i might dispute this. Any help and explanation would be greatly appreciated!

E. Rose
  • 53
  • 4

1 Answers1

-1

This smells like a homework assignment. Never mind, I'll give it a go.

My logic says that the second level would be log(log n), perhaps log(log n)/2. The third would then be log(log(log n)). The final result thus:

log(n) * log(log(n)) * log(log(log(n))).

And by that I'd say that big O is log(n), since this is the biggest factor.

WHY:

How many times will the second loop iterate. First iteration: i = 1, j = 1. It will loop 1 time. The last time: i = n, it will loop log(n) times. On average it will loop log(n)/2 times. So my intuition was wrong...

EDIT:

the third loop runs on average n/2 times.

So, to conclude, log(n)*log(n)n = nlog(n)^2.

But what do I know!?

Jake
  • 843
  • 1
  • 7
  • 18
  • 1. could you please state a reason why the second level is log(log n)? I don't quite get why it should be like that. 2. log(n) * log(log(n)) does not have O(log(n)). Multiplications with non constant factors do count towards the Big O factor. (e.g. n*log(n) is not just n because n is the biggest factor) – ParkerHalo Apr 26 '16 at 11:37
  • The time can't be less than `n` because when `i = n` and `j = i` then the inner loop will run `n` times. – fgb Apr 26 '16 at 12:36