Hacker News Reader

Comment by bogomipz | Hacker News Reader

> "That makes sense. Big-O notation is so overrated."

Can you explain how having a classification that allows one to determine whether something is logarithmic vs vs quadratic is so overrated?

Isn't that a bit like saying "Algebra is so overrated"?

Also Donald Knuth introduced Big O somewhere around the mid 1970s and C++ didn't come along until 1979.

https://en.wikipedia.org/wiki/Big_O_notation#cite_note-knuth...

Also your link is a visualization of ADTs not run times. And while it true that ADTs are chosen for certain guarantees it still depends on how they are used in an algorithm.

View on HN

I think (hope?) that user5994461's post was tongue in cheek.

BTW, you are way off saying Don Knuth introduced Big O. It was invented by physicists and mathematicians like Paul Bachmann and Landau, many decades before the 1970s.

Mathematicians used it for asymptotic expansions of mathematical expressions.

Its use in computer science for algorithmic complexity came later. In fact, I believe in the early TAOCP, Donald did not use big O, but instead would derive the full expression where possible.

I didn't know the OPs post was tongue and cheek. Sometimes it hard to tell : )

Sure "O" goes back to mathematicians in the late 19th century. What I meant was that Knuth introduced Big O(mnicron) in the context of "Computer Science" literature.

This is the source I am referring to from 1976 SIGACT News:

http://www.phil.uu.nl/datastructuren/09-10/knuth_big_omicron...

On page 21 or page 4 of the PDF:

"I would like to close this letter by discussing a competing way to denote the order of function growth. My library research turned up the surprising fact that this alternative approach actually antedates the O-notation itself. "

On page 22 or page 5 of the PDF:

"The main reason why 0 is so handy is that we can use it right in the middle of formulas (and in the middle of English sentences and in tables which show the running times for a family of related algorithms etc.)."

The thing is that an O(n) algorithm can perform faster than an O(1) algorithm simply because Big-O is only comparing different scenarios on a single routine and not how it compares to other algorithms. A slow algorithm might technically be O(1) but that doesn't necessarily make it fast.

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 where there are other things that will necessitate replacing the code before the performance becomes a problem.

But this fact is accounted for in the definition of Big O in the "for all n > k" no?

"f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. "

>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

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.

>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.

Reply on news.ycombinator.com