Big O notation, Complexity

Question

So we're just beginning Big O notation, and we have a question asking this:

What is the worst time complexity for the following loop, if someWork has complexity of O(i), noting that this means that i is the loop counter, so the steps of someWork increases every time the counter does:

while(i < n)
    someWork(...)
    i <-- i + 2

This is obviously written in pseudocode, and I've gotten the easier questions, so I don't believe I have a problem understanding the question, it's this specific one that I'm stuck on. Can I get some help, please?

Thanks so much in advance!

Answer 1

Given that someWork() is dependent on i, and i is, on average, roughly n/2 over all the outer loop iterations, the time complexity is therefore O(n2).

That's because the outer loop depends on n and someWork() (an "inner loop" of some description) also depends on n.

The reasoning behind someWork() being O(n) is as follows.

Let's say n is 8. That means i takes the values {0, 2, 4, 6}, an average of 12 / 4 == 3.

Now let's say n is 16. That means i takes the values {0, 2, 4, 6, 8, 10, 12, 14}, an average of 56 / 8 == 7.

Now let's say n is 32. That means i takes the values {0, 2, 4, ..., 28, 30}, an average of 240 / 16 == 15.

If you continue, you will find that the number of operations performed by someWork() is always n / 2 - 1 hence O(n).

That, in combination with the loop itself being O(n), gives you the O(n2) complexity.

Answer 2

It really depends upon the complexity of someWork(). If someWork() has a loop (or nested loops) inside, the complexity will automatically go from O(n) to O(n^2) or more. If someWork has no loops, this code has O(n) complexity. BTW, I have a hard time trying to understand that last line. Is it part of the loop? Is it assigning anything to i (a typo I mean)?

Answer 3

To simplify the question a bit, suppose the last line is replaced with i <--- i + 1 so that you aren't skipping values of i. Now, how much work is done? The total is,

O(1) + O(2) + O(3) + O(4) + ... + O(n-1) + O(n) = O(1 + 2 + ... + n) = O(n(n+1)/2) = O(n^2).

Now, in your problem, we are leaving out all the even values of i, which is the same as deleting half of the terms. It shouldn't be too hard to see that this should add up to something that is roughly 1/2 as many operations, so we get O(n^2/2) = O(n^2).