Hacker News Reader

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

View on HN

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.

Moat of the time if you have at least several hundred elements. Benchmark it and see.

> The costs just get bigger.

By a constant factor no less (until we get into theoretical physics)

Reply on news.ycombinator.com