IMO, most of these explanations of Big O that I've ever seen have missed the key feature of Big O (the "killer application" if you will): that it's relatively independent of the exact computational model you use. Sure, you have to decide on the broad strokes of your computational model, but you don't need exact, instruction-level details.
This is a pretty huge benefit because it means every CS paper doesn't have to start with a section introducing an abstract machine. The downfall is, of course, that you lose some ability to estimate the potential real-world performance of the algorithm, and the notation itself hides differences between algorithms of the same Big O complexity.
That's not a feature of O; that's simply a feature of leaving stuff out.
O is a simplification of a function, but says nothing about how to construct the function. You need to have your (implicit) computational model before you can start counting critical operations, whether you describe it or not.
This is actually somewhat important, since almost everyone has agreed on a model that, among other things, considers random access, multiplication, hashing, and even explicitly O(log log n) operations to take constant time. It's one of the many reasons why people make incorrect proofs about P=?NP.
edit: If you meant that the simplification abstracts away implementation details like 3n^2+42 vs 2n^2+n, you're right, that's valuable. But I still argue that you ascribe it too much value when it comes to underspecifying your computational model.
Thats a good point, but I've always found the killer app for big O notation is something the answer claims is wrong impossible:
"You can't compare an algorithm to do arithmetic multiplication to an algorithm that sorts a list of integers."
I rarely if ever implement just a multiplier or just a sorter. I end up implementing systems. And if everything in the system is linear or small poly but step #7 is exponential, then comparing Big O for unrelated algos is extremely valuable for me to estimate how long the overall system is going to take and where optimization effort should be placed for best improvement, etc. Don't waste time on making something linear a little faster, when I could be trying to refactor something exponential into something merely poly, somehow (assuming its even theoretically possible per some big O evaluation). Or refactor the whole system to be only poly.
I'll try my hand at a "plain english" explanation of an O(n^2) algorithm.
It's a function which takes a list of numbers as inputs. You give it a list of two numbers. It executes four operations before terminating.
You give it a list of three numbers. It executes nine operations before terminating.
You give it a list of four numbers. It executes sixteen operations before terminating.
You see how the time required grows as n^2 with respect to the input? That's an O(n^2) algorithm, and that's why such an algorithm can be bad. A list of 1,000,000 numbers would require a trillion operations.
The way this can happen is if you write a double-for loop:
for x in input:
for y in input:
...
So, there you go. You probably won't get any plainer of an explanation without becoming oversimplified and losing meaning.
It's plain, I'll give you that. And it gives you an idea. But it's not an explanation as I think it already lost meaning. The explanation is closer to o(n^2) (small o) or maybe Theta(n^2) but still lost the important aspect of only being bound asymptotically.
Almost; r(n) doesn't have to have that property, but it must be bounded above by a function that does have that property. For instance, consider the function r(n) = x*(sin(x)+1).
This is wrong; in the definition it should be "<= some constant", and it should ideally also mention that r and f need to positive, or else take absolute values of them. As an example of a bug in your definition, consider "sin(n) = O(1)". Also, if you say "r(n)/f(n) <= constant", then you don't need to take the limit as "n -> infty", and can talk about "all n".
There have not only been discussions of this before, some previous HN contributions have provided significant criticism and enhancements. If you value the advice and expertise of the HN community at all, you should consider reading some of these earlier comments:
Here are the previous submissions with the most discussion:
This submission of the same item has some discussion, but mostly of the fact that this item is submitted so often, whether it's a problem, and whether we should do something about it, possibly to make HN a better source of curated discussion:
This is a fine example of Stack* giving huge rankings to very bad answers. Big O is about execution time not complexity. (And describing execution time as "time complexity" as some comments do is ridiculous. A lot of something is not more complicated than a little of something. 4 isn't more complex than π -- and no, I'm not saying the reverse is true either.)
A plain English explanation of Big O notation shouldn't take more than a few sentences. It's not that complicated, especially if you don't get into nitty gritty.
Big O is not necessarily about execution time. Also, why is it ridiculous to describe execution time as "time complexity"? From http://en.wikipedia.org/wiki/Analysis_of_algorithms "Usually, the efficiency or running time of an algorithm is stated as a function relating the input length to the number of steps (time complexity) or storage locations (space complexity)."
> Also, why is it ridiculous to describe execution time as "time complexity"?
It's unnecessarily different than the normal definition of "complexity." When you say "complex" in normal conversation, you mean "complicated" or "hard to understand." You would never say "the time complexity of getting to the airport is 30 minutes."
It also begs the question. Wrapping your head around the idea of asymptotic complexity is the hard part of understanding big O. Defining big O in terms of complexity doesn't help if you don't understand the concept of asymptotic complexity yet.
I think the best way to explain this, by far, is with a graph.
If the definition uses "complexity" in this way then it's not using it in the "plain English" sense, but in a specialized sense. Quantity isn't complexity.
Interesting... although his explanation of TSP complexity is unfortunately incorrect (or misstated). The complexity he is describing is specifically for the naive brute force search [1] algorithm for finding the shortest path for TSP. And a 200 city TSP is quite solvable, and often times even by a mobile device like an iPhone 5 [2]! Indeed, no need for all the time in the universe -- lucky for companies like UPS who utilize TSP variants regularly.
Suppose we have a human-written program that's N-bits long. It takes an input, and generates an infinite output by performing some hashing of the input. We run it on an M-bit input to get some output, then stop it manually.
Now suppose we have an input and the output made by this program. But we don't have the program. Suppose we want to discover by brute force what the program was.
The brute-force algorithm will create every possible program up to N bits long, and run each one until either a difference in outputs is found, or it found the correct output, or too much time has passed.
How do you come up with the order-notation for this brute-force algorithm?
I'm sure you know this, but I'd just like to clarify something:
You absolutely can generate only programs that terminate; for instance, throw out any that have recursion or unbounded loops, or use a non Turing complete language that is guaranteed to terminate.
That you can't solve the halting problem in general does not mean that static analysis is fruitless. The answer to "does this terminate" will be yes, no or maybe, almost always in the latter category.
The correct thing to say would be:
If you modify your algorithm to only generate programs without infinite loops, you've most likely thrown out the correct solution.
The "too much time has passed" bound on each iteration guarantees that you don't end up running an iteration forever, and makes the algorithm O(2^N), since the number of programs up to N bits long is 2^(N+1) - 1.
In a tangential note, if P=NP, a sufficiently carefully crafted algorithm very much like that suffices to solve any NP complete problem in polynomial time! (Of course the constants are ridiculously, absurdly large)
> honestly the language of maths too often obfuscates rather than simplifies
This is wrong on so many levels, I don't even know where to begin.
Mathematical formulas and equations are the ultimate tool for simplification and abstraction, the best that humankind could come up with. Explaining mathematical concepts precisely in natural language can be extremely difficult and time-consuming. The only problem is, you have to learn that language, just like any other language. Otherwise, it's like complaining that Japanese "obfuscates" things because you can't read a sentence in Japanese.
This is true, however, mathematical notation is often intrinsically linked to its historical origin and might not be the optimal solution from a usability perspective.
the language of maths is precise yes but its still only one way of looking at maths. there's too many people who think because they have rote learned something it is the only way to see it. its like saying you shouldn't read in Japanese because everything can be adequately describednin English.
Because you've simplified it to the point of being incorrect. First, you've confused big-O, which is an upper bound, with big-theta, which is a strict bound. But leaving that aside, big-O also drops constant factors, and your explanation doesn't. Also, it ignores finitely many 'irregularities', if I have a loop that normally runs n^2 times, except when n=17, 30, or 483, in which case it runs 10 billion times, that's still O(n^2). [That's actually implied by it ignoring constant factors, since you could just crank up the constant to 10 billion/17^2].
Finally, big-O notation describes arbitrary function growth, not just the runtime of some operation when applied to a list. It's used a lot in numerical analysis where you can show that some function can be approximated by, say, x - x^3/6 + x^5/120 + O(x^7).
Thanks for the detail - self taught so I'll defer and try to take on board (also written quickly - I'm sure doing no help to my annoyance that sparked the response - the single minded and to me complex approach of most of these explanations - which I'm sure you'll agree many of which make the same mistakes I have)
one question though -
do you have a source for this 'irregularities' bit? I've never seen that mentioned before at all and a Google hasn't helped. doesn't seem to fit with 'upper bound' and 'worst case'.
[edit: also still not sure how you say im confusing for theta. that's what 'the largest number of times it might' was for.]
If you look at the Wikipedia article on big-O notation, it says that f(x) = O(g(x)) if and only if there exists some M > 0 and x_0 such that |f(x)| < M|g(x)| for all x > x_0. The x_0 is what lets you ignore early irregularities; without it, you couldn't say that sin(x) + 1 is O(x) since there's obviously no M such that sin(0) + 1 < M * 0.
This is a pretty huge benefit because it means every CS paper doesn't have to start with a section introducing an abstract machine. The downfall is, of course, that you lose some ability to estimate the potential real-world performance of the algorithm, and the notation itself hides differences between algorithms of the same Big O complexity.