3 ms·
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 e
by ok123456 16d ago
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.
- koala_man 16d ago> The costs just get bigger. By a constant factor no less (until we get into theoretical physics)
- afdbcreid 16d agoBecause 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.
- mitxela 15d agoMoat of the time if you have at least several hundred elements. Benchmark it and see.