16

I'm asking this question because I am confused about one aspect regarding big O notation.

I am using the book, Data Structures and Abstractions with Java by Frank Carrano. In the chapter on the "Efficiency of Algorithms" he shows the following algorithm:

int sum = 0, i = 1, j = 1
for (i = 1 to n) {
    for (j = 1 to i)
        sum = sum + 1
}

He initially describes this algorithm as having a growth rate of (n2 + n)/2. Which looking at it seems intuitive.

However, it is then stated that (n2 + n)/2 behaves like n2 when n is large. In the same paragraph he states (n2 + n)/2 also behaves much like n2/2. He uses this to classify the above algorithm as O(n2).

I get that (n2 + n)/2 is similar to n2/2 because percentage wise, n makes little difference. What I do not get is why (n2 + n)/2 and n2 are similar, when n is large.

For example, if n = 1,000,000:

(n^2 + n) / 2 =  500000500000 (5.000005e+11)
(n^2) / 2     =  500000000000 (5e+11)
(n^2)         = 1000000000000 (1e+12)

That last one is not similar at all. In fact, quite obviously, it's twice as much as the middle one. So how can Frank Carrano say they are similar? Also, how is the algorithm classified as O(n2). Looking at that inner loop I would say it was n2 + n/2

  • If you are interested I had given an answer for three nested loops with execution tree diagram check A puzzle related to nested loops – Grijesh Chauhan Apr 20 '15 at 13:41
  • 1
    basically the idea is that as n grows, both the functions 'n^2` and your function, behave similarly, ther'es a constant diffidence in their growth rate. If you have a complex expression the function that grows faster dominates. – AK_ Apr 20 '15 at 15:34
  • 1
    @MichaelT : I don't think this is a duplicate of that question, as the other is merely a matter of mis-counting. This is a more subtle question about why the lesser terms (specifically, constant multipliers and lower-degree polynomials) are ignored. The questioner here apparently already understands the issue raised in the other question, and an answer that is sufficient for that question will not answer this one. – sdenham Apr 21 '15 at 11:11
38

When calculating the Big-O complexity of an algorithm, the thing being shown is the factor that gives the largest contribution to the increase in execution time if the number of elements that you run the algorithm over increases.

If you have an algorithm with a complexity of (n^2 + n)/2 and you double the number of elements, then the constant 2 does not affect the increase in the execution time, the term n causes a doubling in the execution time and the term n^2 causes a four-fold increase in execution time.
As the n^2 term has the largest contribution, the Big-O complexity is O(n^2).

  • 2
    I like that, it's getting a little clearer. – Andrew S Apr 20 '15 at 7:29
  • 7
    This is very hand wavy. Could be true or could be false. If you can take a tiny amount of math see one of the answers below. – usr Apr 20 '15 at 21:04
  • 2
    This reasoning is too vague: it would mean that we could conclude that O(n * log n) = O(n), which is not true. – cfh Apr 21 '15 at 6:18
  • It may not be the most precise answer or the most semantically correct, but what is important here is that it led me to begin understanding the central point and I think that was the author's aim. It's deliberately vague as the details can often distract from the core principles. It's important to see the wood for the trees. – Andrew S Apr 21 '15 at 22:15
  • Bart was really talking about terms, not factors. Understanding that, we cannot conclude that O(n * log n) = O(n). I think this gives a good explanation of the rationale behind the definition. – Mark Foskey Apr 1 '18 at 1:58
10

The definition is that

f(n) = O(g(n))

if there exists some constant C > 0 such that, for all n greater than some n_0, we have

|f(n)| <= C * |g(n)|

This is clearly true for f(n) = n^2 and g(n) = 1/2 n^2, where the constant C should be 2. It's also easy to see that it's true for f(n) = n^2 and g(n) = 1/2 (n^2 + n).

  • 4
    "If there exists some constant C>0 such that, forr all n," should be "If there exits some constants C, n_0 such that, for all n>n_0," – Taemyr Apr 20 '15 at 12:16
  • @Taemyr: As long as the function g is nonzero, that's actually not needed as you can always increase the constant C to make the statement true for the finitely many first n_0 values. – cfh Apr 20 '15 at 12:18
  • No, we as long as we are looking at functions there is not a finite number of potential n_0 values. – Taemyr Apr 20 '15 at 12:20
  • @Taemyr: n_0 is a finite number. Choose C = max{ f(i) / g(i) : i = 1, ..., n_0 }, and then the statement will always hold for the first n_0 values, as you can easily check. – cfh Apr 20 '15 at 12:22
  • In CS this is less of a concern because n is usually input size, and hence discreet. In which case one can choose C such that n_0=1 works. But the formal definition is any n larger than some threshold, which removes a whole lot of nitpicking in applying the definition. – Taemyr Apr 20 '15 at 12:22
6

When talking about complexity, you're only interested in the time factor changes based on the number of elements (n).

As such you can remove any constant factor (like the 2 here).

This leaves you with O(n^2 + n).

Now, for a reasonable large n the product, i.e. n * n, will be significantly bigger than just n, which is the reason you're allowed to skip that part as well, which leaves you indeed with a final complexity of O(n^2).

It is true, for small numbers there'll be a significant difference, but this becomes more marginally the bigger your n becomes.

  • How big does n have to be for the difference to become marginal? Also, why is the /2 removed, its existence halves the value? – Andrew S Apr 20 '15 at 6:41
  • 6
    @AndrewS Because Big O Notation talks about growth. Dividing by 2 is irrelevant outside the context of benchmarks and timestamps because it ultimately doesn't change growth rate. The largest component, however, does and so that's all you keep. – Neil Apr 20 '15 at 8:26
  • 2
    @Niel, brilliant so clear. I wish the books would put it like that. Sometimes I think the authors know too much that they forget that mere mortals don't posses their functional knowledge and therefore do not make clear important points, but instead bury it in some formal mathematical description or omit it all together believing it to be implied. – Andrew S Apr 20 '15 at 10:39
  • I wish I could upvote this answer more than once! @Neil, you should be writing the Big O books. – Tersosauros Feb 17 '18 at 17:00
3

It's not that "(n² + n)/2 behaves like n² when n is large", it's that (n² + n)/2 grows likeas n increases.

For example, as n increases from 1,000 to 1,000,000

(n² + n) / 2  increases from  500500 to  500000500000
(n²) / 2      increases from  500000 to  500000000000
(n²)          increases from 1000000 to 1000000000000

Similarly, as n increases from 1,000,000 to 1,000,000,000

(n² + n) / 2  increases from  500000500000 to  500000000500000000
(n²) / 2      increases from  500000000000 to  500000000000000000
(n²)          increases from 1000000000000 to 1000000000000000000

They grow similarly, which is what Big O Notation is about.

If you plot (n²+n)/2 and n²/2 on Wolfram Alpha, they are so similar that they're difficult to distinguish by n=100. If you plot all three on Wolfram Alpha, you see two lines separated by a constant factor of 2.

  • This is good, it makes it very clear to me. Thanks for replying. – Andrew S Apr 21 '15 at 18:45
2

It just looks like you need to work out the big O notation a bit more. How convenient this notation is, it is very misleading because of the use of an equal sign, which is not used here to denote the equality of functions.

As you know, this notation expresses an asymptotic comparisons of functions, and writing f = O(g) means that f(n) grows at most as fast as g(n) as n goes to infinity. A simple way to translate this is to say that the function f/g is bounded. But of course, we have to take care of the places where g is zero and we end up with the more robust definition that you can read almost everywhere.

This notations turns out to be very convenient for computing – this is why it is so widespread – but it should be handled with care as the equal sign we see there does not denote an equality of functions. This is pretty much like saying that 2 = 5 mod 3 does not imply that 2 = 5 and if you are keen on algebra, you can actually understand the big O notation as an equality modulo something.

Now, to go back to your specific question, it is totally useless to compute a few numeric values and compare them: however large one million is, it does not account for asymptotic behaviour. It would more useful to plot ratio of the functions f(n) = n(n-1)/2 and g(n) = n² – but in this special case we can readily see that f(n)/g(n) is smaller than 1/2 if n > 0 which implies that f = O(g).

To improve your understanding of the notation, you should

  • Work with a clean definition, not a fuzzy impression based on things being similar – as you just experienced it, such a fuzzy impression does not work well.

  • Take some time to work out examples in details. If you work out as little as five examples within a week, it will be enough to improve your confidence. This is an effort which is definitely worth.


Algebraic side note If A is the algebra of all functions Ν→Ν and C the subalgebra of bounded functions, given a function f the set of functions belonging to O(f) is a C-submodule of A, and computation rules on the big O notation just describe how A operates on these submodules. Thus, the equality we see is an equality of C-submodules of A, this is just another sort of modulus.

  • 1
    That Wikipedia article is difficult to follow after the first small peice. It was written for accomplished mathematicians by accomplished mathematician and is not the kind of introductory text I would expect from an encyclopedic article. Thanks for your insight though its all good. – Andrew S Apr 21 '15 at 19:11
  • You overestimate the level in the text of Wikipedia! :) It is not that well written, for sure. Graham, Knuth and Patashnik wrote a lovely book “Concrete Mathematics” for students in CS. You can also try “the Art of Computer Programming” or a number theory book written in the 50s (Hardy & Wright, Rose) as they usually target high-school student level. You do not need to read the full book, if you pick one, just the part about asymptotic! But before you need to decide how much you need to understand. :) – Michael Le Barbier Grünewald Apr 21 '15 at 22:58
1

I think you misunderstand what the big O notation means.

When you see O(N^2) it basically means: when the problem gets 10 times as large, the time to solve it will be : 10^2 = 100 times as large.

Let's punch 1000 and 10000 in your equation: 1000: (1000^2 + 1000)/2 = 500500 10000: (10000^2 + 10000)/2 = 50005000

50005000/500500 = 99,91

So while the N got 10 times as big, the solutions got 100 times as big. Hence it behaves: O(N^2)

1

if n was a 1,000,000 then

(n^2 + n) / 2  =  500000500000  (5.00001E+11)
(n^2) / 2      =  500000000000  (5E+11)
(n^2)          = 1000000000000  (1E+12)

1000000000000.00 what?

While the complexity gives us a way to predict a real-world cost (seconds or bytes depending on whether we are talking about time complexity or space complexity), it doesn't give us a number of seconds, or any other particular unit.

It gives us a degree of proportion.

If an algorithm has to do something n² times, then it will take n²×c for some value of c that is how long each iteration takes.

If an algorith has to do something n²÷2 times, then it will take n²×c for some value of c that is twice as long as each iteration takes.

Either way, the time taken is still proportional to n².

Now, these constant factors are not something we can just ignore; indeed you can have the case where an algorithm with O(n²) complexity does better than one with O(n) complexity, because if we are working on a small number of items then impact of the consant factors is greater and can overwhelm other concerns. (Indeed, even O(n!) is the same as O(1) for sufficiently low values of n).

But they are not what complexity tells us about.

In practice, there are a few different ways we can improve the performance of an algorithm:

  1. Improve the efficiency of each iteration: O(n²) still runs in n²×c seconds, but c is smaller.
  2. Reduce the number of cases seen: O(n²) still runs in n²×c seconds, but n is smaller.
  3. Replace the algorithm with one that has the same results, but lower complexity: E.g. if we could repalce something O(n²) to something O(n log n) and hence changed from n²×c₀ seconds to (n log n)×c₁ seconds.

Or to look at it another way, we've got f(n)×c seconds being taken and you can improve performance by reducing c, reducing n or reducing what f returns for a given n.

The first we can do by some micro-opts inside a loop, or using better hardware. It will always give an improvement.

The second we can do by perhaps identifying a case where we can short-circuit out of the algorithm before everything is examined, or filter out some data that won't be signficant. It won't give an improvement if the cost of doing this outweighs the gain, but it will generally be a bigger improvement than the first case, especially with a large n.

The third we can do by using a different algorithm entirely. A classic example would be replacing a bubble sort with a quicksort. With low numbers of elements we may have made things worse (if c₁ is greater than c₀), but it generally allows for the biggest gains, especially with very large n.

In practical use, complexity measures allow us to reason about the differences between algorithms precisely because they ignore the matter of how reducing n or c will help, to concentrate on examinging f()

  • "O(n!) is the same as O(1) for sufficiently low values of n" is just wrong. There has to be a better way to explain that "when n is kept sufficiently low, Big-O doesn't matter". – Ben Voigt Apr 21 '15 at 1:08
  • @BenVoigt I've yet to come across one with the same rhetorical impact as this had when I first read it; it's not originally mine, I stole it from Eric Lippert, who may have originated it or may have taken it from someone else. Of course it references jokes such as "π equals 3 for small values of π and large values of 3" which is older still. – Jon Hanna Apr 21 '15 at 9:00
0

Constant factor

The point of big O notation is that you can choose an arbitrarily large constant factor so that O(function(n)) is always larger than C*function(n). If algorithm A is a billion times slower than algorithm B, then they have same O complexity, as long as that difference doesn't grow when n grows arbitrarily large.

Let's assume a constant factor of 1000000 to illustrate the concept - it's a million times larger than neccessary, but that illustrates the point that they're considered irrelevant.

(n^2 + n) / 2 "fits inside" O(n^2) because for any n, no matter how large, (n^2+n)/2 < 1000000*n^2.

(n^2 + n) / 2 "doesn't fit" a smaller set, e.g. O(n) because for some values (n^2+n)/2 > 1000000*n.

The constant factors can be arbitrarily large - an algorithm with running time of n years has O(n) complexity which is "better" than an algorithm with a running time of n*log(n) microseconds.

0

Big-O is all about "how complicated" an algorithm is. If you have two algorithms, and one takes n^2*k seconds to run, and the other takes n^2*j seconds to run, then you can argue about which one is better, and you might be able to make some interesting optimizations to try to affect k or j, but both of these algorithms are dead slow compare to an algorithm that takes n*m to run. It doesn't matter how small you make the constants k or j, for a big enough input the n*m algorithm will always win, even if m is quite large.

So we call the first two algorithms O(n^2), and we call the second O(n). It nicely divides the world up into classes of algorithms. This is what big-O is all about. It's like dividing vehicles up into cars and trucks and busses etc... There's a lot of variation between cars, and you can spend all day arguing about whether a Prius is better than a Chevy Volt, but at the end of the day if you need to put 12 people into one, then this is a rather senseless argument. :)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.