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