That makes sense. Big-O notation is so overrated.
A little bit of history: C++ programmers were always able to choose the right containers simply by using this image, since long before the invention of Big-O.
A little bit of history: C++ programmers were always able to choose the right containers simply by using this image, since long before the invention of Big-O.
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.
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.
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.)."
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.
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.
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
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.
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.
"f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. "