Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Big-O notation explained by a self-taught programmer

justin.abrah.ms

Post reply on HN
Print view View original

51–58 of 58 posts

Re: Big-O notation explained by a self-taught programmer

#51

Post by stouset »

FreeFull wrote: post #45
_greim_ wrote: post #42

Earlier quoted context omitted.

Yup. Achieving a better big-O could for example be the difference between something being possible or not, whereas fine-tuning an algo without altering its big-O might be the difference between needing five servers or ten. Still relevant, but a different class of relevance.

It can also be the case that an algorithm with a worse big-O complexity might actually be better because all your inputs are small and the constant multiplier is lower than the more complicated, better big-O algorithm

This suggestion gets trotted out in every discussion on Big-O. In 16 years of doing this professionally, I have not once encountered a situation where that would have been relevant. Any case where it even remotely might have been, the algorithm wouldn't have been hot enough to warrant considering it at all.

Re: Big-O notation explained by a self-taught programmer

#52

Post by tscs37 »

pluma wrote: post #31
gk101 wrote: post #27

Earlier quoted context omitted.

Yes, however big O notation isn't about which programs run faster, it's about how the runtime of a program changes in response to the input size

...which is irrelevant depending on the bounds of the input size. It boils down to optimization. There's no point in spending time optimizing for Big-O if the input size will be so small the difference between O(n²) and O(n log n) doesn't matter. As with all optimizations, there are situations where it matters a lot. But in the real world there are plenty of situations where the time is better spent elsewhere or wher…

>O(n²) and O(n log n)

What about O(n!) and O(logn)?

I think that will probably explode even at microscopic input sizes.

Even in the real world, understanding what O is helps a lot. That doesn't mean you should use it everywhere or that you have to.

But it means you should understand how your code scales. Efficient code scales because it has a low order, inefficient code doesn't scale because it has a high order.

And if you replace the code, what have you done but change the order of the algorithm?

Computers are just a collection of functions with some order, some are O(n!), some O(1), some O(infinity) and some others are O(nlogn). Big-O is everywhere no matter if you admit it or not, so understanding it can be a big help to understand why Code A is faster or slower than Code B

Re: Big-O notation explained by a self-taught programmer

#53

Post by tscs37 »

hellofunk wrote: post #17
mrcactu5 wrote: post #7

Don't you want to know if your recipe takes 10 minutes or 10 hours to cook?

That would be nice to know, but Big-O won't tell you that. It makes no time guarantees, it only provides an idea of an implementation. An O(1) algorithm sounds great, until you realize that 1 means 1 hour for that particular algorithm, while a competing algorithm's O(n) might mean n seconds in reality. What's in the parenthesis is not a measure of a unit of time, which is why Big-O fanatics often miss the bigger pict…

>An O(1) algorithm sounds great, until you realize that 1 means 1 hour for that particular algorithm, while a competing algorithm's O(n) might mean n seconds in reality.

Well, I'm not trying to miss the bigger picture, but if you're going to scale that your O(n) algorithm will quickly take longer than a O(1) algorithm.

I mean, let's just take a hashtable as example. This hash takes 1 hour to complete while you can search the list in milliseconds.

But what if the list has billions and billions of entries and it takes longer than 1 hour?

As some others said, Big-O is not something you use to choose one algorithm over the other, it's something you use to choose an algorithm that scales well and has acceptable performance.

O(n) vs O(1) is a rather tame comparison, what if your competing algorithm is a O(n!) or worse?

Re: Big-O notation explained by a self-taught programmer

#54

Post by pluma »

tscs37 wrote: post #52
pluma wrote: post #31

Earlier quoted context omitted.

...which is irrelevant depending on the bounds of the input size. It boils down to optimization. There's no point in spending time optimizing for Big-O if the input size will be so small the difference between O(n²) and O(n log n) doesn't matter. As with all optimizations, there are situations where it matters a lot. But in the real world there are plenty of situations where the time is better spent elsewhere or wher…

>O(n²) and O(n log n) What about O(n!) and O(logn)? I think that will probably explode even at microscopic input sizes. Even in the real world, understanding what O is helps a lot. That doesn't mean you should use it everywhere or that you have to. But it means you should understand how your code scales. Efficient code scales because it has a low order, inefficient code doesn't scale because it has a high order. And…

To address your first point: There is an amazing amount of software where even O(n!) vs O(log n) doesn't matter. There is also of course a lot of software where it does. There is even more software where it does matter in some parts of the code but doesn't in others.

Every optimization has a cost. Time is a finite resource. Time spent optimizing one thing could be spent optimizing something else or implementing a new feature or fixing a bug.

That said, the original argument isn't that that which Big-O notation represents is generally irrelevant. The argument is that the formalism of Big-O notation itself is generally irrelevant (except where it isn't, obviously).

You don't need CS101 to understand that a nested for-loop probably scales worse than a single if-statement. Or that looping over the input twice in succession is probably faster than nesting those loops. Or that only looking at half the input is faster than looking at all the inputs, and so on.

To put it in other words: you can figure out that something that scales from an ant to an elephant to a skyscraper scales worse than something that scales in multiples of ducks without having to use a ruler or charts. Big-O is the more accurate tool but there is a tremendous amount of situations where you don't need an accurate tool and a vague understanding of the same thing the tool would measure is entirely sufficient.

Re: Big-O notation explained by a self-taught programmer

#55

Post by tscs37 »

pluma wrote: post #54
tscs37 wrote: post #52

Earlier quoted context omitted.

>O(n²) and O(n log n) What about O(n!) and O(logn)? I think that will probably explode even at microscopic input sizes. Even in the real world, understanding what O is helps a lot. That doesn't mean you should use it everywhere or that you have to. But it means you should understand how your code scales. Efficient code scales because it has a low order, inefficient code doesn't scale because it has a high order. And…

To address your first point: There is an amazing amount of software where even O(n!) vs O(log n) doesn't matter. There is also of course a lot of software where it does. There is even more software where it does matter in some parts of the code but doesn't in others. Every optimization has a cost. Time is a finite resource. Time spent optimizing one thing could be spent optimizing something else or implementing a new…

>The argument is that the formalism of Big-O notation itself is generally irrelevant (except where it isn't, obviously).

That sentence kinda defeats the argument itself. If it's irrelevant except where it is not, then your argument is obviously true.

We could also say that some number X is always not 1 except when it is.

>You don't need CS101 to understand that a nested for-loop probably scales worse than a single if-statement.

That is true, but it's just Big-O applied via intuition rather than learning.

Big-O is mostly the expression of intuition for some people.

Re: Big-O notation explained by a self-taught programmer

#56

Post by achr2 »

BjoernKW wrote: post #35
achr2 wrote: post #21

The thing I always run into when discussing big-O are people (good programmers even) who think all O(x) algorithms have the same efficiency. I find it very frustrating when someone says my streamlined O(N) algo with 5 operations has the same efficiency as their O(N) algo with 20 extra function calls and operations. Big-O is not the only determining factor...

In a way Big-O notation intentionally glosses over these differences. At a large scale 5 vs 20 per instance of n doesn't matter. It might matter for practical purposes but Big-O really is about making broad distinctions.

I definitely agree with you, my comment was simply to show that there are a lot of people who use Big-O as a metric at a level where it shouldn't be applied.

Re: Big-O notation explained by a self-taught programmer

#57

Post by FreeFull »

stouset wrote: post #51
FreeFull wrote: post #45

Earlier quoted context omitted.

It can also be the case that an algorithm with a worse big-O complexity might actually be better because all your inputs are small and the constant multiplier is lower than the more complicated, better big-O algorithm

This suggestion gets trotted out in every discussion on Big-O. In 16 years of doing this professionally, I have not once encountered a situation where that would have been relevant. Any case where it even remotely might have been, the algorithm wouldn't have been hot enough to warrant considering it at all.

One example would be multiplying large matrices together. A common algorithm used is https://en.wikipedia.org/wiki/Strassen_algorithm with a big-O complexity of around O(n^2.8074). https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_a... has a complexity of around O(n^2.375477), but the constant factors are so large it is currently never better to use it over the Strassen algorithm.

Re: Big-O notation explained by a self-taught programmer

#58

Post by sn9 »

code777777 wrote: post #33
Waterluvian wrote: post #25

Earlier quoted context omitted.

As a self taught programmer who did no math in university, the most valuable thing to me was the discovery that the math really isn't scary. Once you understand the symbols and notation, most concepts are rather easy, given you commit time to learning it. I strayed away for so long until I watched the MIT lecture series on algorithms and it all just clicked. The best feeling was was seeing the math on the chalk board…

Would you please share the link to the MIT lecture series? It may help the rest of us too. Thanks!

Coursera also has two great sets of Algorithms courses: one on analysis and one on implementation (the latter by Sedgewick).

Self-taught programmers really have an embarrassment of riches these days.

Post reply on HN