0

I've been searching for a while on how to calculate complexity of algorithms.. and while there are some great explanations, I just don't seem to understand exactly how it works.. so I thought maybe on this example, someone can clarify it for me

void test(int n){
for ( int i = 1; i <= n; i++, n=n/2)
    for(int j = 1; j <= n; j++)
       ..O(1)..
        }
Johnny Blaze
  • 13
  • 2
  • 2
    Possible duplicate of [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – Whatatimetobealive Jan 28 '19 at 18:28

1 Answers1

0

The first time the outer loop runs, the inner loop will run n times.
The second time the outer loop runs, the inner loop will run n/2 times.
The third time the outer loop runs, the inner loop will run n/4 times.
The fourth time the outer loop runs, the inner loop will run n/8 times.
. . .
The last time the outer loop runs, the inner loop will run 1 time.

When you sum the series you get

n + n/2 + n/4 + n/8 + ... = 2n

The body of the inner loop executes a total of 2n times, so the complexity of the algorithm is O(n).

Bill the Lizard
  • 398,270
  • 210
  • 566
  • 880
  • @JohnnyBlaze No, not when `n` is being cut in half every time through the outer loop. The first iteration is the only time "something simple" actually happens the full `n` times. – Bill the Lizard Jan 28 '19 at 19:21
  • let me edit that "something simple" it's confusing the hell out of me – Johnny Blaze Jan 28 '19 at 19:25
  • any chance you can refer me to somewhere I can learn more? I'm just starting and it's very confusing – Johnny Blaze Jan 28 '19 at 19:27
  • @JohnnyBlaze Outside of text books, [What is a plain English explanation of “Big O” notation?](https://stackoverflow.com/a/487278/1288) is the best resource that I know. This problem is tricky because the outer loop appears to be O(n), but it's really O(log n). Worse, the inner loop by itself is O(n), but that n keeps changing. That's why I approached it with the sum-of-series method. – Bill the Lizard Jan 28 '19 at 19:33