alt Hacker NewsMost algorithm analyses don't incorporate memory hierarchies. I'm not sure what the point of this post was.
If you are really concerned about it, compute the empirical roofline for your machine.
Also, if the point is to point out memory hierarchies, it's not 'quadratic performance.' The algorithm doesn't behave differently once it spills over. The costs just get bigger.
Replies
koala_man • today at 8:13 PM
> The costs just get bigger.
By a constant factor no less (until we get into theoretical physics)
Because complexity models that involve memory hierarchy are an active research area and are super complex. Also, "plain" complexity is still useful: despite the constant factor, at large N (and this is sometimes a real possibility) the complexity will still win. For example, despite binary search being less cache-friendly (it can be made more with some tricks but not the same), it still defeats linear search most of the time.