News for hackers. Stuff that matters.
Re:The true cost of linked lists by TchoBeer on Monday June 06, 2022 @08:57AM (#31639867)
>Big-O assumes all "operations" are equally costly. That's not the case on real hardware, and pretty much never has been

Assuming that operations take a linear amount of time (i.e. multiplying three times takes three times as long as multiplying once) this won't affect the asymptotic behavior.

>Big-O assumes that only asymptotic behavior matters, but real-world workloads have finite input sizes.

This is definitely something to keep in mind when analyzing algorithms, but that does not imply asymptotic complexity is not useful when analyzing performance. There are other measures (e.g. how an algorithm performs on a random small input, or maybe your domain is restricted somewhat) and sometimes those measures areore useful than big O, but big O remains useful, it just is not the end all be all.

Re:The true cost of linked lists by inetknght on Monday June 06, 2022 @09:54AM (#31640506)
> Assuming that operations take a linear amount of time (i.e. multiplying three times takes three times as long as multiplying once) this won't affect the asymptotic behavior.

This assumption is demonstrably broken if the first multiplication is a cache miss but the other multiplications then aren't -- an easy example is when the other two multiplications have data on the same cache line as the first multiplication's data.

Re:The true cost of linked lists by erk__ on Monday June 06, 2022 @10:08AM (#31640695)
That is probably a reason big-O is used, the big-O definition which says that they most be upper-bounded by a linear multiplier. So even if the second and third multiplication is faster it will not change the asymptotic behavior.