5 ms·
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
by user5994461 10y ago
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.
http://homepages.e3.net.nz/~djm/containerchoice.png http://homepages.e3.net.nz/~djm/containerchoice.png
- bogomipz 10y ago> "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-12 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.
- mikebenfield 10y agoI 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.
- BeetleB 10y agoMathematicians 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.
- bogomipz 10y agoI 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.pdf 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.)."
- hellofunk 10y agoThe 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.
- gk101 10y agoYes, 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
- pluma 10y ago...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.
- bogomipz 10y agoBut 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. "
- tscs37 10y ago>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
- Buttons840 10y agoTip: If you're asked about Big-O in an interview, and your rusty, at least determine whether the algorithm is sub-linear or super-linear. Just knowing this is 80% of what you need to be aware of in industry IMHO.
- MOARDONGZPLZ 10y agoMaybe you're being hyperbolic (and maybe I'm being pedantic), but from what I recall Knuth was the first to describe complexity notation in the late-60s or early-70s in The Art of Computer Programming. This definitely predates C++.