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

They don't count the additions or shifts because they're both linear time operations, and thus provably at least as fast as multiplication (both in an asymptotic and exact sense). In any case where multiplication is super-linear, this means that addition and shifting are are not the temporal bottleneck at any stage in the algorithm where you have a constant number of those operations surrounding at least one multiplicative recursive call (on numbers of similar magnitudes).

If additions were truly free, an even easier optimal algorithm would just be repeated addition involving zero multiplications.



Consider applying for YC's Fall 2026 batch! Applications are open till July 27.

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

Search: