Plain English explanation of Big O(stackoverflow.com)
stackoverflow.com
Plain English explanation of Big O
http://stackoverflow.com/a/487278
46 comments
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.
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.
"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.
How about this one?
http://discrete.gr/complexity/
And if you don't like it, you can edit it too:
https://github.com/dionyziz/complexity-article
http://discrete.gr/complexity/
And if you don't like it, you can edit it too:
https://github.com/dionyziz/complexity-article
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:
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:
...
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.
I always found the mathematical definitions of asymptotic notation the most clear:
An algorithm with runtime r(n) is "big O" of f(n) if the limit as n -> infinity of r(n) / f(n) <= some constant.
EDIT: See replies below.
An algorithm with runtime r(n) is "big O" of f(n) if the limit as n -> infinity of r(n) / f(n) <= some constant.
EDIT: See replies below.
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".
> I always found the mathematical definitions of asymptotic notation the most clear
Which definition of asymptotic notation is there besides the mathematical definition, which by definition defines it? :)
Which definition of asymptotic notation is there besides the mathematical definition, which by definition defines it? :)
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:
https://news.ycombinator.com/item?id=1520552 (24 comments, 1242 days ago)
I found them by using this search:
https://www.hnsearch.com/search#request/all&q=title%3A%28pla...
Here are some other submissions:
https://news.ycombinator.com/item?id=695988 (4 comments)
https://news.ycombinator.com/item?id=2344181
https://news.ycombinator.com/item?id=3807175
https://news.ycombinator.com/item?id=3846993
https://news.ycombinator.com/item?id=5164236
https://news.ycombinator.com/item?id=5636683
https://news.ycombinator.com/item?id=5778469
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:
https://news.ycombinator.com/item?id=5785523 (24 comments)
The answer seems to be "No".
Additionally, you might be interested in reading these:
https://news.ycombinator.com/item?id=4655061 : Big-O Misconceptions
https://news.ycombinator.com/item?id=5770232 : What does O(log n) mean, exactly?
Here are the previous submissions with the most discussion:
https://news.ycombinator.com/item?id=1520552 (24 comments, 1242 days ago)
I found them by using this search:
https://www.hnsearch.com/search#request/all&q=title%3A%28pla...
Here are some other submissions:
https://news.ycombinator.com/item?id=695988 (4 comments)
https://news.ycombinator.com/item?id=2344181
https://news.ycombinator.com/item?id=3807175
https://news.ycombinator.com/item?id=3846993
https://news.ycombinator.com/item?id=5164236
https://news.ycombinator.com/item?id=5636683
https://news.ycombinator.com/item?id=5778469
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:
https://news.ycombinator.com/item?id=5785523 (24 comments)
The answer seems to be "No".
Additionally, you might be interested in reading these:
https://news.ycombinator.com/item?id=4655061 : Big-O Misconceptions
https://news.ycombinator.com/item?id=5770232 : What does O(log n) mean, exactly?
Thank you!
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.
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.
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.
[1] http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common...
[2] http://www.math.uwaterloo.ca/tsp/iphone/
[1] http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common...
[2] http://www.math.uwaterloo.ca/tsp/iphone/
[deleted]
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?
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?
Since you're bounding (with a constant) the time each iteration can take, this is just O(2^n).
EDIT: I suppose if the time bound per program is a parameter "m" that you can vary, then it's actually O(m*2^n).
Without the bound, this algorithm is unlikely to work, since programs can run indefinitely.
If you modify your algorithm to only generate programs without any infinite loops, you've solved the halting problem, which is impossible.
EDIT: I suppose if the time bound per program is a parameter "m" that you can vary, then it's actually O(m*2^n).
Without the bound, this algorithm is unlikely to work, since programs can run indefinitely.
If you modify your algorithm to only generate programs without any infinite loops, you've solved the halting problem, which is impossible.
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.
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.
>If you modify your algorithm to only generate programs without any infinite loops, you've solved the halting problem, which is impossible.
Nonsense, there is no reason you cannot design an algorithm that uses a halting oracle. Running that algorithm may be difficult though.
Nonsense, there is no reason you cannot design an algorithm that uses a halting oracle. Running that algorithm may be difficult though.
I'm confused. Why is the output infinite? Do we know when the hashing was stopped?
I'm not sure this is a decidable problem with just the information you gave.
Did you just make up the problem, or is that inspired from a real world situation?
I'm not sure this is a decidable problem with just the information you gave.
Did you just make up the problem, or is that inspired from a real world situation?
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)
http://lucatrevisan.wordpress.com/2010/03/07/on-the-necessit...
http://lucatrevisan.wordpress.com/2010/03/07/on-the-necessit...
O(2^n) where n is the number of bits?
[deleted]
I loved that cartoon!
Oh, wait...
Oh, wait...
The author of this answer, cletus, is also a member of this community and has quite a high karma.
See his content here: https://news.ycombinator.com/user?id=cletus
See his content here: https://news.ycombinator.com/user?id=cletus
Aaaand it's wrong like 99.9% other explanations:
f(n)=O(n^2) is actually NOT f(n) asymptotically grows as fast as n^2, it is f grows “no faster” than n^2.
“As fast as” is f(n)=Θ(n^2)
Edit: oh, and Big-O is not “a relative representation of the complexity of an algorithm”
f(n)=O(n^2) is actually NOT f(n) asymptotically grows as fast as n^2, it is f grows “no faster” than n^2.
“As fast as” is f(n)=Θ(n^2)
Edit: oh, and Big-O is not “a relative representation of the complexity of an algorithm”
a lot of words for "the larges number of times a loop/operation might have to run, for a list of size 'n'"
honestly the language of maths too often obfuscates rather than simplifies
honestly the language of maths too often obfuscates rather than simplifies
> 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 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).
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.]
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.
You're right about the theta thing, my mistake.
You're right about the theta thing, my mistake.
[deleted]
Speaking of plain English, Knuth's use of Big-Oh notation for asymptotics brings to mind another domain of human activity altogether.
The SICP does some fun puzzles in thinking like this.
This is at least a 3rd degree repost.
Thanks for sharing!
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.