Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

The article is conflating theoretical algorithm analysis and low level implementation details.

Big O analysis is a theoretical measurement of algorithm performance. By definition it ignores details like memory access speed, the exact instructions used, and other details of specific hardware architectures.

Real life algorithm implementations obviously need to deal with those low level implementation details, but that doesn't change the theoretical analysis. It's easy enough to find (or design) machines without cache where this difference in memory speed doesn't exist.



"RAM+arithmetic"-style complexity analysis in terabyte-scale-and-above problems is unable to distinguish between very practical and absolutely impractical algorithms. "square-root ideal cache hierarchy + arithmetic" has much better distinguishing power (for parallel programs, you also need to remember to bound throughput, e.g. Bernstein's area*time, for similar reasons).




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: