2 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 2mo 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 2mo ago> The costs just get bigger. By a constant factor no less (until we get into theoretical physics)
- afdbcreid 2mo 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 2mo agoMoat of the time if you have at least several hundred elements. Benchmark it and see.