3 ms·
Trivial nitpick: since this is binary search, the base for the logarithm is 2, not e. So it would be 2^M.
by Liquid_Fire 7y ago
Trivial nitpick: since this is binary search, the base for the logarithm is 2, not e. So it would be 2^M.
- tempguy9999 7y agoNitpick 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. (https://en.wikipedia.org/wiki/The_Siphonaptera> https://en.wikipedia.org/wiki/The_Siphonaptera>
- thethirdone 7y agoNitpick 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.