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

When Big O Fools You

jackmott.github.io

Post reply on HN
Print view View original

31–40 of 134 posts

Re: When Big O Fools You

#31

Post by stcredzero »

valarauca1 wrote: post #27
jandrese wrote: post #17

Earlier quoted context omitted.

Also, Big-O notation is a theoretical construct for thinking about complexity that works well for academic proofs but glosses over many real world considerations. Those ignored constant factors can be large and the datasets are not always large enough to amortize their cost.

Furthermore amortization isn't always accounted for in Big-O. Inserting into into the head of a linked list is O(1), and for a vector it is O(n). But on modern hardware vector inserts are much faster. If your software engineering begins and ends with Big-O notation, your likely doing a terrible job. Measure, and test. Always.

I would say, "If your software engineering begins and ends with [jargon] you're likely doing a terrible job. Measure, and test. Always."

As a field, do we measure and test the effect of using various programming paradigms, patterns, and coding standards? I don't think most companies do this. Most developer decisions are made by "gut." As a field, we are still more like the "before" of Moneyball than the after.

Re: When Big O Fools You

#32

Post by mezuzza »

justusw wrote: post #25

This article points out a few right things, but also skips over the wrong parts. Namely, the amortised time complexity of dynamic lists. Amortised analysis treats operations not as single events but looks at the time complexity over the span of many operations (through something called "Accounting"). An initial "investment" of array over-allocation will be amortised by inserting, but only over time. Inserting into an…

This point should be understood very clearly: The article isn't wrong that an ArrayList has O(n) for a single insertion. However, the article misses that amortized analysis shows that the same structure can be made to have O(n) for n insertions as well. In effect, ArrayLists can be thought to have O(1) insertion time in practice meaning that all you are comparing are the differences in constants between the two structures.

I think the biggest takeaway from this isn't that big-O can fool you (which it very well can), but that misunderstanding analysis can lead to poor decisions.

A better argument for big-O fooling you can be found using Quicksort and any proper O(n Log(n)) sorting algorithm. Quicksort will outperform most in practical cases, but is technically O(n^2) in the worst case (average case O(n Log(n)).

Re: When Big O Fools You

#33

Post by tillytal »

JohnLeTigre wrote: post #23
ncw33 wrote: post #12

In no so many words, the article is pointing out that O(n) + O(1) is not necessarily quicker than O(n) + O(n): both add to O(n) (since only the highest-order factor matters), and the constant factor is unsurprisingly better for array lists. He's not benchmarking an O(1) operation against an O(n), or anything surprising, or even pointing out a "hidden" O(n) operation, it's simply a demonstration that O(n) + O(1) = O(n…

Of course this was a single example. The main point is that the big O notation ignores the cache misses. For example: - try writing a quicksort as a template to avoid the comparison function calls - in the sorting loop, switch to an insertion sort when buckets have You will see speed improvements of 2 to 3 times faster than a vanilla implementation of quicksort. Although this approach is slightly more complex on the…

Surely the main point is that

    O(n) + O(n) = O(2n) = O(n) = O(n + 1) = O(n) + O(1)
and the constant factors left out of O() often dominate execution time.

Cache performance is just one example of a constant factor, right?

Re: When Big O Fools You

#34

Post by altendo »

A lot of the focus in the HN comments is on ArrayLists, but I'm curious why the author chose to give linked lists an O(1) insert time. In some implementations (doubly linked list, inserting at the head of the list) I can see the O(1) time, but when appending to the end it also is O(n) because one has to traverse the entire list of elements before updating the link at the end of the list. Might just be nitpicking here but that might also be affecting the author's results.

Re: When Big O Fools You

#35

Post by CountHackulus »

Big O isn't fooling you, it's giving you a one-function explanation of how the algorithm runs on an idealized system as the size of the problem increases. There's other systems you can simulate for big O, but the math is much harder and you wouldn't generally use it unless you're doing something complex like a cache-oblivious algorithm.

If you're using solely big O to decide on an algorithm, you're fooling yourself. If performance is an issue, profile, benchmark, study, don't guess.

Re: When Big O Fools You

#36

Post by _benedict »

stcredzero wrote: post #31
valarauca1 wrote: post #27

Earlier quoted context omitted.

Furthermore amortization isn't always accounted for in Big-O. Inserting into into the head of a linked list is O(1), and for a vector it is O(n). But on modern hardware vector inserts are much faster. If your software engineering begins and ends with Big-O notation, your likely doing a terrible job. Measure, and test. Always.

I would say, "If your software engineering begins and ends with [jargon] you're likely doing a terrible job. Measure, and test. Always." As a field, do we measure and test the effect of using various programming paradigms, patterns, and coding standards? I don't think most companies do this. Most developer decisions are made by "gut." As a field, we are still more like the "before" of Moneyball than the after.

There's a third option: analysis and understanding.

This seems to be entirely forgotten by the "measure, test" crowd - the scientific method requires a hypothesis to test for measurements to be meaningful, and separately not all things that are produced are "tested" in every aspect, since many things are well established, and the application of that existing theoretical framework makes measurement and testing a waste of time.

Having a theoretical understanding of the thing you care about is far more important than the "measure, test" step - which is certainly important, but by itself of really limited power.

Re: When Big O Fools You

#37

Post by jameshart »

justusw wrote: post #25

This article points out a few right things, but also skips over the wrong parts. Namely, the amortised time complexity of dynamic lists. Amortised analysis treats operations not as single events but looks at the time complexity over the span of many operations (through something called "Accounting"). An initial "investment" of array over-allocation will be amortised by inserting, but only over time. Inserting into an…

Insertion at the head of a dynamic list avoids the issue of amortized complexity, though, since every element in the array needs to be copied on every insert, whether a new array needed to be allocated or not. Unless you're concerned about the time complexity of the memory allocator?

Re: When Big O Fools You

#38

Post by SamReidHughes »

qwertyuiop924 wrote: post #26

Here's a question: How often does this matter ? No, not that big O can fool you. That always matters. How often does it matter that non-contigouous memory access is slow? Really. How much do those few useconds really matter? In most apps, I would guess that a CPU cache miss isn't noticable by humans. Yes, non-contiguous structures are significantly slower, but if you don't need to be as fast as possible, eliminating…

Big O notation is used to describe whatever you want it to. The average case is the usual choice, in fact.

Re: When Big O Fools You

#40

Post by tbirdz »

altendo wrote: post #34

A lot of the focus in the HN comments is on ArrayLists, but I'm curious why the author chose to give linked lists an O(1) insert time. In some implementations (doubly linked list, inserting at the head of the list) I can see the O(1) time, but when appending to the end it also is O(n) because one has to traverse the entire list of elements before updating the link at the end of the list. Might just be nitpicking here…

Just keep a pointer to the head and tail of the list. You can then append to either end of the list in O(1). When you put a new node at the tail end, use the tail pointer to get to the tail node instead of walking the whole list. Of course, you need to make sure the head/tail pointers are always updated to point to the current head/tail of the list.
Post reply on HN