What is the Big-O complexity of the code?

Question

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
            j=j*2;
      }
}

I am having trouble generalizing it.

Count the amount of iterations. The inner loop is independent of `i`, you do `j = j*2` and `j++` each iteration. Try it out on paper and you realize that this reaches `n` in about `sqrt(n)` steps. (`1, 3, 7, 15, 31, 63, ...`). So each outer loop generates `O(sqrt(n))` many inner iterations. The outer loop runs `n` times. So you have `O(n * sqrt(n))` which is `O(n^(3/2))`. The `j++` is a bit nasty but that doesnt change the fact that the order of magnitude is still `O(sqrt(n))` which is all that counts. — Zabuzard, Aug 31 '20 at 13:53
Its actually `log_2` and not `sqrt`, rest of the argumentation is still correct though. — Zabuzard, Aug 31 '20 at 14:02
Note that, since your code does not actually do anything except modifying a local-only variable, a compiler can completely replace the code by nothing, since its not doing anything that affects an external variable at all. So technically you could argue that it might be `O(1)` after optimization by some specific compiler for a specific programming language. — Zabuzard, Aug 31 '20 at 14:06

score 4 · Accepted Answer · edited Aug 31 '20 at 14:04

4

If we count the number of multiplication the program does, the complexity will be n * log2(n)

You do n times the inner loop (i scales with n), and the inner loop repeats as long as j <= n. j increase exponentially

1, 3, 7, 15, 31, 63, 127, ... = (2^n) - 1

Which is 2^n scaling, so double the value of n makes the inner loop iterate once more.

log2(n * 2) = log2(n) + 1

edited Aug 31 '20 at 14:04

Zabuzard

answered Aug 31 '20 at 13:59

Martial P

Can you please explain the n*log2(n) part? – Rajeev R Aug 31 '20 at 14:29
1

@RajeevR it is already explained. Is I said, you do 1 mor iteration of the j loop every time you double the n value. The corresponding function of that behavior is log2(n). As you reapeat it n times, the number of iterations will scale according to n*log2(n). However I have no clue of what are you trying to do. – Martial P Aug 31 '20 at 14:38
Thank you. I am just solving questions to find the big O time complexity of small piece of code. This is one of them. Thanks, you helped me a lot. – Rajeev R Aug 31 '20 at 14:43

1 Answers1