2 ms·
I see other people pointing out that it isn't true for small n, but this isn't true for large n either. The article's binary search implementation is O(n!) (and
by lern_too_spel 6y ago
I see other people pointing out that it isn't true for small n, but this isn't true for large n either. The article's binary search implementation is O(n!) (and also O(log(n)), among many others). Its linear search is O(n) (and many others). I can find an N large enough such that the binary search will outperform the linear search for any n>N.
- xxpor 6y agoSure, but that's not really the point. It's more running more code == probably bad for speed. There's obviously a lot of detail there, like time/space tradeoffs, large constants, etc.
- lern_too_spel 6y agoI'm saying that an O(n!) algorithm is not necessarily faster asymptotically than an O(n) algorithm and that saying it is shows a fundamental misunderstanding of the definition. This is regardless of time/space tradeoffs and large constants.