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!

let's say n is a big positive integer and i is 0. so, the loop may go on for n/2 times, since i is increased by 2 everytime. — Santhosh, Jan 15 '14 at 03:33
Ok, for example, the first question was "What is the worst case time complexity of this loop if 'someWork' is an 'O(1)' algorithm? This is the last question in a series of questions that increased in difficulty I got the answer to be 'O(n/2)' — Auxilio, Jan 15 '14 at 03:52
If the answer is O( n/2 ), it means that `someWork()` doesn't have complexity O( i ) but O( 1 ). The thing is : O( n/2 ) pretty much means O( n ). — Bernard Saucier, Jan 15 '14 at 17:57
Thanks for that, I had another class today and realized that mistake. Great reply :) — Auxilio, Jan 15 '14 at 19:15

score 1 · Answer 1 · answered Jan 15 '14 at 03:28

1

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)?

answered Jan 15 '14 at 03:28

dotNET

33,414
24
162
251

It won't necessarily go from O(n) to O(n^2) if there is a nested for loop. What if the nested for loop iterates over an empty list? His pseudocode not sufficient – The Internet Jan 15 '14 at 03:30
@TheInternet: Complexities do not care for best case scenarios. It is normally the average and worst time that matters. See http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o?rq=1. – dotNET Jan 15 '14 at 03:39
The pseudocode itself may not be sufficient but the text clearly states that someWork is O(i) which is effectively O(n) in this scenario. I'd vote this up except dotNET seems to have missed the fact the complexity of someWork has actually been specified. – paxdiablo Jan 15 '14 at 03:45
With the specified complexity of someWork, what would the resulting O notation be? – Auxilio Jan 15 '14 at 03:58

paxdiablo · Accepted Answer · 2014-01-15T04:01:14.210

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(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.

edited Jan 15 '14 at 04:01

answered Jan 15 '14 at 03:36

paxdiablo

854,327
234
1,573
1,953

I like this, but we aren't looking for the average, we're looking for the worst case. Is this the same in this instance? Sorry... first time really working with O notation. – Auxilio Jan 15 '14 at 04:03
@Auxilio, don't make the mistake of thinking my use of the word "average" relates to the complexity. I'm using the average just to show that the `someWork()` function depends on `n`. It's similar to `1+2+3+4+5 = 3*5` (middle number by count), `1+2+3 = 2*3`, 1+2+...+n = (n+1)/2 * n`. – paxdiablo Jan 15 '14 at 04:06

score 0 · Answer 3 · answered Jan 15 '14 at 07:22

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).

Big O notation, Complexity

3 Answers3