53

I know the big-O complexity of this algorithm is O(n^2), but I cannot understand why.

int sum = 0; 
int i = 1; j = n * n; 
while (i++ < j--) 
  sum++;

Even though we set j = n * n at the beginning, we increment i and decrement j during each iteration, so shouldn't the resulting number of iterations be a lot less than n*n?

Ayman Nedjmeddine
  • 11,521
  • 1
  • 20
  • 31
Omar N
  • 1,720
  • 2
  • 21
  • 33
  • 2
    How many times is the loop executed, given an n? – asjo Nov 22 '15 at 19:06
  • 29
    Yes, it's less than `n*n`, but the number of iterations is _proportional_ to `n*n`. That's what the big-O notation indicates. – nicola Nov 22 '15 at 19:07
  • I suppose it depends on the value of n, but if n is 5 for example, I believe it will be executed around 12 times. – Omar N Nov 22 '15 at 19:07
  • 2
    @OmarN Yes, the point of O()-notation is how the "time" grows as n does, so start by calculating how many times the loop executes, expressed in terms of n, rather than examples, and then you are very close to your answer. – asjo Nov 22 '15 at 19:10
  • 8
    Whether you increment `i` by 1, 5, or 10,000, doubling `n` will still increase the running time by a factor of 4, which is the hallmark of an O(n^2) algorithm. – chepner Nov 22 '15 at 19:24
  • 8
    Hint: at the end of this loop, [`sum == n*n / 2`](http://ideone.com/EsW7cV). – geometrian Nov 23 '15 at 00:53
  • 10
    To be clear, the big-O complexity is also O(n^3), O(e^n), and O(n!^n!). – djechlin Nov 23 '15 at 02:00
  • @djechlin Huh? What do you mean? – RHawkeyed Nov 23 '15 at 14:10
  • 5
    @RHawkeyed big-O provides upper bounds. They need not be "tight". – djechlin Nov 23 '15 at 14:29
  • 2
    @djechlin Ah you're right. Tight bound is just so often implied, and also seems so much more useful. – RHawkeyed Nov 23 '15 at 14:53
  • @RHawkeyed Note that there is a notation for when you want to say that the bound is tight, namely Ө(n^2) (that's a capital Theta symbol, look up "big theta notation"). For most computer applications, though, this is a bit too strong, since there may be special inputs for which the program runs faster than expected. (This doesn't happen in the example, though, because n is the only input and the output function is known to be exactly n^2/2, as imallett says.) – Mario Carneiro Nov 23 '15 at 17:09
  • 1
    @RHawkeyed it really isn't implied most of the time... the sequence 0,1,0,2,0,3,... is O(n) but this isn't a tight bound at all. You would see a lot more analyses ruling out "best cases" if it were implied. – djechlin Nov 23 '15 at 18:03
  • There is no such things as *the* "Big-Oh complexity". I recommend you (all) check out the reference material on [algorithm analysis](http://meta.cs.stackexchange.com/a/844/98) and [asymptotics](http://meta.cs.stackexchange.com/a/846/98) on [cs.SE]. – Raphael Nov 24 '15 at 08:17
  • @MarioCarneiro No, you can use Ө for worst-case bounds. See [here](http://cs.stackexchange.com/questions/23068/how-do-o-and-relate-to-worst-and-best-case). – Raphael Nov 24 '15 at 08:19
  • @djechlin Forgive my ignorance, but my limited experience with big-O is for comparing algorithms to be used on large datasets, and in those cases it was implied. Can you maybe give an example of when it is useful to write the big-O complexity as fx O(n^3) while O(n^2) would also bound? – RHawkeyed Nov 24 '15 at 13:05
  • @Raphael Of course it is possible to measure different things, but "complexity of the algorithm" here is usually referring to the whole input space. You would need to say best/worst/average-under-X-distribution complexity specifically if that is what you want to say. – Mario Carneiro Nov 24 '15 at 13:58
  • 1
    @RHawkeyed The primary application is for when you want to use it as a hypothesis, for example "if f,g in O(n^3) then f+g in O(n^3)". In your application you might have f in O(n^3) and g in O(n^2), and you use the weakening rule to say that g is also in O(n^3) so you can apply the theorem. – Mario Carneiro Nov 24 '15 at 14:06
  • @Raphael actually a better argument against using Ө in standard arguments is that it doesn't play as well with common operations. For example if f,g in O(h) then f-g in O(h), but the same is not true for Ө, it could be any lower complexity. So you have to carefully analyze the whole algorithm at once in order to properly determine (worst-case) Ө, while O can just be determined by putting together the components of the algorithm (although the resulting order may be overly pessimistic). – Mario Carneiro Nov 24 '15 at 14:19
  • @MarioCarneiro ""complexity of the algorithm" here is usually referring to the whole input space" -- that does not make much sense. What would that mean, formally? Usually, people use "complexity" for asymptotic worst-case running time bounds. (I for one think that one should not use "complexity" for algorithm costs at all.) – Raphael Nov 24 '15 at 15:14
  • @MarioCarneiro That's the worst argument I've ever seen in this context. 1) Arithmetics with Landau-terms are flawed as they are. 2) There is no good reason against using Ө besides not being able to prove it. 3) Your "strategy" for determining O-bounds sounds naive and fuzzy; what does "putting together" even mean here? I recommend you drop by on [cs.SE]. We have experts in algorithm analysis (and asymptotics) there; you may learn something. – Raphael Nov 24 '15 at 15:17
  • @Raphael It's mathematically well-defined, but on reflection it's not as common as I originally thought, with the usual interpretation being "worst case" instead. (The definition of "the algorithm is Ө(f) over the whole input space", where f is a function of n, is that there exists an N, a, b such that for all inputs i of size n >= N, the running time T(i) of the algorithm satisfies a |f(n)| <= T(i) <= b|f(n)|.) As for my argument, it is perhaps overly terse due to the character limit but it is perfectly valid, "putting together" here refers to composition of functions. – Mario Carneiro Nov 24 '15 at 15:27
  • @MarioCarneiro I see, that is a workable definition. It would be an "all-case" bound which I don't think I've seen used, implicitly or explicitly. Most people would say that best-case-Ө = worst-case-Ө, which is equivalent. – Raphael Nov 24 '15 at 15:29
  • I am aware that finding the big-O of a given algorithm is in general an undecidable problem (because the halting problem is undecidable), so there is no general rule that applies to all circumstances. However, it is well-known that a few simple rules will handle the majority of common cases, particularly if the algorithm uses "structured programming" tactics like simple loops with known bounds and sequential composition. – Mario Carneiro Nov 24 '15 at 15:35
  • @Raphael Yes, using the obvious analog for all-case big-O and big-Ω, we have all-case-O = worst-case-O and all-case-Ω = best-case-Ω, so all-case-Ө = worst-case-O + best-case-Ω (which also implies that each of these is also worst-case-Ө and best-case-Ө). Of course, an all-case-Ө may not exist for a given algorithm, if the best and worst cases differ asymptotically, while a best-case-Ө or worst-case-Ө always exists (any simple function of n is Ө of itself). – Mario Carneiro Nov 24 '15 at 15:42
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/96055/discussion-between-raphael-and-mario-carneiro). – Raphael Nov 24 '15 at 16:44
  • I'm voting to close this question as off-topic because it belongs on CS.SE. – Kyle Strand Nov 24 '15 at 17:49

7 Answers7

114

During every iteration you increment i and decrement j which is equivalent to just incrementing i by 2. Therefore, total number of iterations is n^2 / 2 and that is still O(n^2).

Miljen Mikic
  • 14,765
  • 8
  • 58
  • 66
  • 4
    In other word `i` increases linearly and `j` increases quadratic. Quadratic trumps linearly and it's why it's O(n^2) – jean Nov 23 '15 at 19:04
  • 2
    @jean `i`'s starting value is a constant that does not depend on `n`. So you shouldn't compare `i` and `j` like that. – Dmytro Shevchenko Nov 26 '15 at 21:14
  • 1
    Ye I can because I'm comparing not the values the variables are setted but how they control the iteration. Note one increases and another decreases until they "collide". `i` Starts from a constant but grows linearly and `j` decreases lineraly but the initial value grows from quadratic. You can easily keep the logic just by setting `j` to the same constant and increasing it untl `i+j < n^2`. The decreasing `j` and while condition as they are rwitten in the question are just to check if you are paying attention to the logic – jean Nov 27 '15 at 09:51
53

big-O complexity ignores coefficients. For example: O(n), O(2n), and O(1000n) are all the same O(n) running time. Likewise, O(n^2) and O(0.5n^2) are both O(n^2) running time.

In your situation, you're essentially incrementing your loop counter by 2 each time through your loop (since j-- has the same effect as i++). So your running time is O(0.5n^2), but that's the same as O(n^2) when you remove the coefficient.

Máté Juhász
  • 2,197
  • 1
  • 19
  • 40
Ben Rubin
  • 6,909
  • 7
  • 35
  • 82
  • Nothing to do with the coefficient in this case. O(0.5n^2) is O(0.5n^3). – djechlin Nov 23 '15 at 18:04
  • 2
    @djechlin you seem to be spending a lot of your time checking this question and "schooling" people. How about spending just a few extra seconds to better articulate your comment suggestions? Also, you are quite wrong in equating quadratic and cubic time complexities as equals in the O notation space. See https://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities for a list. – marknuzz Nov 23 '15 at 21:10
  • @Nuzzolilo I posted an answer, what more do you want? These comments should be here for future readers who ought to see this asterisk. To your last point, all slippers are shoes, not all shoes are slippers :) (and furthermore "= O(f(n))" is an [abuse of notation](https://en.wikipedia.org/wiki/Abuse_of_notation)) – djechlin Nov 23 '15 at 21:18
  • 2
    @djechlin Nuzzolilo is right. There **is** a difference between O(n^2) and O(n^3). Coefficients don't matter in big-O notation, however powers do. Don't confuse coefficients and constants. – Ben Rubin Nov 23 '15 at 21:24
  • @BenRubin I agree there is a difference. O(n^2) is O(n^3). O(n^3) is not O(n^2). Slippers are shoes. When dealing with big-O the [abuse of notation](https://en.wikipedia.org/wiki/Abuse_of_notation) that "= O(n^3)" is taken to mean "is in the class" is invoked. Most of math communication does not invoke this. – djechlin Nov 23 '15 at 21:26
  • Sorry my link should be more specific https://en.wikipedia.org/wiki/Abuse_of_notation#Big_O_notation – djechlin Nov 23 '15 at 21:28
  • 4
    In the context of your expanded explanation, you are indeed correct in equating O(n^2) = O(n^3), but the original one liner at the top of the thread was not explained well. You can be the most world-class big shot in the room, but if you can't articulate your ideas well, your knowledge is useless. If you think of everyone else who disagrees with your ethos as a troll, then you have cut yourself off from a vital source of outside learning, and you will not retain your top big shot status for long if you do that. Just some food for thought. – marknuzz Nov 23 '15 at 21:44
  • 8
    @djechlin O(n²) is not O(n³), but it is a subset of it. – Paul Nov 23 '15 at 22:04
11

You will have exactly n*n/2 loop iterations (or (n*n-1)/2 if n is odd). In the big O notation we have O((n*n-1)/2) = O(n*n/2) = O(n*n) because constant factors "don't count".

m3tikn0b
  • 1,298
  • 8
  • 16
10

Your algorithm is equivalent to 

while (i += 2 < n*n) 
  ...

which is O(n^2/2) which is the same to O(n^2) because big O complexity does not care about constants.

Salvador Dali
  • 214,103
  • 147
  • 703
  • 753
4

Let m be the number of iterations taken. Then,

i+m = n^2 - m

which gives,

m = (n^2-i)/2

In Big-O notation, this implies a complexity of O(n^2).

Ujjwal Aryan
  • 3,827
  • 3
  • 20
  • 31
4

Yes, this algorithm is O(n^2).

To calculate complexity, we have a table the complexities:

O(1) O(log n) O(n) O(n log n)
O(n²) O(n^a) O(a^n) O(n!)

Each row represent a set of algorithms. A set of algorithms that is in O(1), too it is in O(n), and O(n^2), etc. But not at reverse. So, your algorithm realize n*n/2 sentences.

O(n) < O(nlogn) < O(n*n/2) < O(n²)

So, the set of algorithms that include the complexity of your algorithm, is O(n²), because O(n) and O(nlogn) are smaller.

For example: To n = 100, sum = 5000. => 100 O(n) < 200 O(n·logn) < 5000 (n*n/2) < 10000(n^2)

I'm sorry for my english.

Francisco Manuel Garca Botella
  • 761
  • 9
  • 6
0

Even though we set j = n * n at the beginning, we increment i and decrement j during each iteration, so shouldn't the resulting number of iterations be a lot less than n*n?

Yes! That's why it's O(n^2). By the same logic, it's a lot less than n * n * n, which makes it O(n^3). It's even O(6^n), by similar logic.

big-O gives you information about upper bounds.

I believe you are trying to ask why the complexity is theta(n) or omega(n), but if you're just trying to understand what big-O is, you really need to understand that it gives upper bounds on functions first and foremost.

djechlin
  • 59,258
  • 35
  • 162
  • 290
  • Nailed it that "big-O gives you information about upper bounds". What's this about O(6^n) though? This is a power function, not an exponential. – aaaarrgh Nov 23 '15 at 09:26
  • @aaaarrgh 6^n grows faster than any polynomial. So anything in O(n^c), where c is a constant, will also be in O(6^n). – Taemyr Nov 23 '15 at 09:27
  • 4
    @djechlin See the XY-problem and realise that OP is trying to learn why O(n^2) is the most narrow upper bound. – Taemyr Nov 23 '15 at 09:28
  • @Taemyr There's *plenty* of answers doing that and while they are all technically correct none of them seem to be actually working with the right definition of big-O. It seemed like an answer solving X should be contributed as well. – djechlin Nov 23 '15 at 14:26
  • @Taemyr actually I am not so sure my answer fails XY. If someone is trying to learn why something is big-O doesn't it stand to reason that the definition of big-O actually comes up at some point. The Y is basically a red herring here and it's unfortunate we're diving into a technical part of the definition without giving the *obvious* and correct answer first. Seems OP is going to walk away from this question thinking O means theta. That shouldn't happen when you ask why small thing = O(big thing). – djechlin Nov 23 '15 at 14:36
  • @djechlin It fails (or at least failed) the XY-problem, because it gives a correct answer without explaining what is wrong with the question. Your answer doesn't really go into the definition of big-O; you state that his algo is in O(n^2) and also in O(n^3) without showing how that follows from said definition. – Taemyr Nov 23 '15 at 14:43
  • 4
    @djechlin Theta can be significantly harder to work with than big-O. For this reason IMO the pedantict correction to OP's question is not "you should ask why algo is Theta(n^2)" but "you should ask why O(n^2) is the tightest upper bound". – Taemyr Nov 23 '15 at 14:46
  • @taemyr feel free to post your own answer that avoids concepts like theta notation that are too pedantic. – djechlin Nov 23 '15 at 17:48
  • upper bounds? why not lower bounds? – bubakazouba Nov 24 '15 at 07:59
  • @bubakazouba big-Omega gives lower bounds. – djechlin Nov 24 '15 at 20:15
  • @djechlin y does it say in ur answer upper bounds? – bubakazouba Nov 24 '15 at 20:25
  • @bubakazouba because big-O gives upper bounds. https://en.wikipedia.org/wiki/Big_O_notation – djechlin Nov 24 '15 at 22:51
  • @Taemyr you are technically correct that O(6^n) is also *some* valid answer for an upper bound. But it is not a *useful* upper bound -- we could also say that this algorithm is O(n^n^n^n^n), but that would not be useful either since it is not the smallest provable upper bound. Adding in some arbitrary bigger upper bound on a big-O question is a great way to muddy the waters for someone asking a question, instead of clarifying why the lowest upper bound holds. – aaaarrgh Nov 30 '15 at 22:11
  • @aaaarrgh idk I just felt we should all walk away from this question actually knowing what big-O means, but maybe I am just being too academic after all. – djechlin Nov 30 '15 at 22:18
  • @aaaarrgh it's also wrong to say an upper bound is not "useful" if it is not the "smallest provable upper bound," in fact really the entire point of using big-O notation is you do not need to use the smallest provable bound for many results, but I might just being academic again. – djechlin Nov 30 '15 at 22:20
  • 1
    You're talking about what Big-O means in a high-level computer science class, where you distinguish between Big-O, Big-Theta, and Big-Omega. In the real world, programmers generally say "Big-O" when what they really mean is probably Big-Theta. StackOverflow is mostly populated by programmers working at real jobs in the real world, not grad students. Which is why everyone is arguing with you. :) – Kip Nov 30 '15 at 22:48