4 ms·

>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

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

inetknght 4y ago
> 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.
- erk__ 4y ago
  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.