Big O notation, Complexity

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!

Solution

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(n²).

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(n²) complexity.