Plain English explanation of Big O? (2009) | Hacker News Reader

Plain English explanation of Big O? (2009)

stackoverflow.com

158 pointstarny24 comments

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 some of the previous submissions:

https://news.ycombinator.com/item?id=695988 (4 comments)

https://news.ycombinator.com/item?id=1520552 (24 comments, 1000 days ago)

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 (submitted just yesterday)

Here's a pretty tight, explicit search for the same item:

https://www.hnsearch.com/search#request/all&q=title%3A%2...

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?

Maybe HN should introduce "it was here" button, for people with enough carma.

Some ability to merge discussions has previously been discussed, but lots of people on HN think it's not a problem.

Here are a few times it's been mentioned:

https://news.ycombinator.com/item?id=122751

https://news.ycombinator.com/item?id=2766949

https://news.ycombinator.com/item?id=2826798

https://news.ycombinator.com/item?id=3018533

https://news.ycombinator.com/item?id=3657234

https://news.ycombinator.com/item?id=5382906

Here's a poll asking what people think:

https://news.ycombinator.com/item?id=2822041

Here's a submission from me asking for exactly this feature, with it's associated discussion:

https://news.ycombinator.com/item?id=3349371

Here's a counter viewpoint from someone I generally respect, but who disagrees strongly with me on this topic:

https://news.ycombinator.com/item?id=3357125

Well played.

well it clearly is a problem. I'm not clicking each link in that.

Seeing a grouped list of links all at once is much more convenient than seeing (or missing, most likely) each link individually over the course of a few months.

Wow, I remembered including this in the 4th issue of Hacker Monthly[1] 3 years ago(!).

1. Hacker Monthly #4 (I just made it free), if you like to read this in PDF/MOBI/EPUB format along with few others timeless HN articles: http://hackermonthly.com/issue-4.html

Here's what I told my parents over dinner one day:

You have a problem that needs to be solved and a way of solving it that takes a certain amount of time. I the problem grows, how much longer will it take to solve with that same method? If the problem is twice as big, will it take twice as long?

For example, I need to move a steak from one plate to another. My method is to use a knife and fork to cut the steak into bite sized pieces and move each piece to the other plate. If I have two steaks, I can expect this method to take twice as long. What if I have 10 steaks? It might take a bit of work to make room to properly cut a steak. At 20 steaks, I probably just don't have room on the plate anymore and it takes much longer than 20 times the time to move those steaks than it did to move 1 steak.

Now let's say my method is to just dump the contents of the first plate onto the second plate. If I have two steaks this takes about as long to do. What if I have 10 steaks, or 20? It starts getting clumsy and the time it takes to move them using this new method gets longer at a predictable rate. At 200 steaks I probably can't just dump one plate onto the other, I can't even lift the plate!

The question then is, up to how many steaks is the second method better than the first? Is it always better as the number of steaks goes up? Is there a better steak moving method? What if we change the container from plates to something else?

Come on, this was posted less than a month ago here. My browser even still marks it as visited.

I missed it back then. I read this posting and got value from it.

So, for future reference, is one supposed to know in advance what news or articles one is looking for and search HN first? Im confused as to how this is supposed to work. If I missed it a month ago, am I not allowed to see it posted again, by some one else who might well have missed it a month ago?

Or, do you suggest that moderators look out for duplicates, block the links and comments, and merely post a link back to the original?

Or should people who don't read every article, and log it in some way just not be here?

But, people have up voted it. So, it must still have value. Are those people not wanted? Are they wrong in some way?

I don't understand the criticism at all. Cant you just ignore the article, instead of belittling those who did get value form a second posting?

I don't think it's a criticism of the people who read the article, rather of those who posted it. Just like logging a bug, you should make sure someone hasn't logged it already. A bit of repetition on a yearly basis would be fine, but if all popular articles or topics were posted monthly or more with no added information, you can see how it would kill HN. And just like the bug example, there would be benefit if all comments were funneled to existing threads.

And then it gives the chance for the old-timers to lord over the newbies here, so there's a bit of that.

This particular article, however, is somewhat of a special case. The fact that programmers don't seem to understand big-O notation is a concern to me. I think it is as fundamental to programming as knives are to a chef, something that should be learned in any CS study, or intuitive to any self-taught programmer.

Less than a month ago? It was submitted just yesterday!

https://news.ycombinator.com/item?id=5778469

Welcome to Hacker News. I'm serious, this is pretty common.

I agree. It's like an old story will pop up and those that are new to the community will jump all over it, thinking its words from God or something.

Used to be you would post something that already was posted, the first comment would call you out for it, and then it would naturally disappear. Now we are learning Big 0 every other day.

This is why karma points are BS.

Surely someone out there has pinterested this along with that old relational-databases-as-Venn-diagrams post into a giant textbook of accessible computer science.

(This is a serious request.)

I think this shows how powerful mathematical notation really is once you understand the concepts (which i admit is not easy). One formal definition versus pages of explanations. It's the same with other programming concepts like monads. Many have written blog posts explaining monads in Haskell and those are great to learn how to apply them but in the end the formal definitions explain them best.

http://en.wikipedia.org/wiki/Big_O_notation - see "formal definition". The core of it is one sentence in english, and it's even shorter if you choose to use only mathematical notation.

All you need to know in the context of applying this to algorithms is that there has to be some notion of "size" for the problem, and the time it takes for the algorithm to complete is a function of that size.

Once you internalize that, understanding complexity analysis will be much easier. You don't have to memorize complexities of common algorithms.

I'm not really sure why it's so difficult to wrap your head around this concept, but apparently it is difficult. This is the second time I'm seeing this link on HN in the past month, I think.

O is how you choose to work on something, like how you choose to wash the dishes.

n is how many dishes you have to wash.

Which is faster? Washing, then drying, then putting away each dish one after the other, or washing all of the dishes, then drying all of the dishes, then putting them all away?

If n is 1 then either method is the same. If n is 10 then maybe the first approach is a little less efficient, but when n is 100 then obviously the batched approach is more efficient.

Big O notation is just the formal way of comparing which algorithm is more efficient when applied to large data sets.

Sorry if I've misread your example, but I think this isn't quite correct. While the "batch" method of dish-washing (washing all at once, then drying all at once) is probably more convenient and efficient for humans, if you were to formalize your "dish-washing" algorithms, I believe both of them would have running times in the same class of functions -- ie the same big Oh.

In pseudo-java-code:

    void washDishes(Dish[] dishes) {
        for(Dish d : dishes) {
            Sponge s = getSponge();
            s.wash(d);
            Towel t = getTowel();
            t.dry(d);
        }
    }
    
    void washDishes(Dish[] dishes) {
        Sponge s = getSponge();
        for(Dish d : dishes) {
            s.wash(d);
        }
        Towel t = getTowel();
        for(Dish d in dishes) {
            t.dry(d);
        }
    
    }

Maybe, in practical terms, there would be differences in efficiency, but those are exactly the kinds of constant factors big Oh is meant to abstract, and for the purpose of example, both of these are O(n) given input size (number of dishes) of n.

I hesitated to post this comment, since it's kind of a "well, actually"[0], but unless I'm mistaken this example is fundamentally flawed.

[0] http://tirania.org/blog/archive/2011/Feb-17.html

In your first method, you call getSponge() and getTowel() d times each, but in your second method you only call each once. That would be significant for large values of d, if I'm not mistaken.

edit: using "d" to refer to the number of dishes here. that could have caused confusion, my bad.

That's actually exactly what I was trying to point out. It may be significant practically, or might not, and definitely would be if you were really washing the dishes ;) But in terms of big Oh, they're the same.

If you assume that all of the methods (getSponge, getTowel, wash, dry) do the same amount of "work", ie take the same amount of time to execute, then the first function takes 4d units of time (continuing to use d as the number of dishes). The second takes 2d+2 units of time. We define these as (mathematical) functions in terms of d, which compute the time spent for a given input size:

    f(d) = 4d
    g(d) = 2d+2

It's possible to prove that both of these function are O(d).

The formal definition of O(n) is:

    f(x) = O(n) if and only if there exists some constant c
    and some value x0 such that, for all x > x0:
    f(x) <= c * n.

It's a way to talk about the growth rate of functions, what people usually mean when they say some algorithm is O(n) is that the function calculating the runtime based on input size is O(n).

This is pretty trivial to show with f and g above, pick c=5, x0=1.

Roughly, you can drop additive and multiplicative constants when computing the "big Oh" of a function. I'm leaving out an awful lot of formal mathematical details here, partly because I'm rusty, but also because all of this is much better presented elsewhere, in numerous algorithms textbooks and courses. (btw it's possible I've made a mistake in the above, for which I hope you'll forgive me)

Lots of people would recommend the big white book from MIT, but I'm fond of "The Algorithm Design Manual" which is less formal and rigorous, and thus perhaps a little better suited to professional software developers who are just brushing up.

http://ocw.mit.edu/courses/electrical-engineering-and-comput...

http://www.algorist.com/

Makes sense. I think I glanced over the text before and after your pseudo-code too fast. You're absolutely right about the constants not affecting the Big Oh part. For some reason I initially interpreted your comment to say "these two algorithms are equally fast". My mistake :o

if plain english could handle big O, we'd probably be programming in it ?

Reply on news.ycombinator.com