Re:On Binary Search
by Liquid_Fire on Thursday October 31, 2019 @07:30AM
(#21407585)
Trivial nitpick: since this is binary search, the base for the logarithm is 2, not e. So it would be 2^M.
[ Parent
| on HN ]
Re:On Binary Search
by tempguy9999 on Thursday October 31, 2019 @08:01AM
(#21407754)
Nitpick upon nitpick, the base may be 2 rather than e but IIRC the difference between lg(n) and log2(n) is a constant, and the log/lg term dominates, so it still is 0(log). I think.
Big fleas have little fleas upon their backs to bite 'em \ And little fleas have lesser fleas, and so, ad infinitum.
Re:On Binary Search
by thethirdone on Thursday October 31, 2019 @08:45AM
(#21408110)
Nitpick on Nitpick on Nitpick, it is indeed O(2^m) and not O(e^m). Those are not the same complexity.
Logs get to not care, but when we exponentiate it matters.