3 ms·
Thats not a good example for Big O because number of operations computes exactly to logN in worst case. Try with mergesort and see how it ends being nlogn
by dominotw 11y ago
Thats not a good example for Big O because number of operations computes exactly to logN in worst case.
Try with mergesort and see how it ends being nlogn
- george_soros 11y agoIsn't O(log n) just an upper bound limit ? So isn't it more correct to say, that in worst case the number of steps are < O(log n) ?
- roywiggins 11y agoBig-O describes an upper limit in itself. Something that is O(N) is also O(2^N). No less-than needed, it's included in the definition of big-O.
- justinlardinois 11y agoYes, but context matters; Big O is often used informally. The interviewer's going to look at you weird when you tell him the O(N) algorithm is O(2^N).
- schoen 11y agoWe have the same problem with things being "in NP". It's clear that all of P is in NP, but not clear whether all of NP is in P. But people often say "NP" with the implication of "(apparently, as far as we know) not in P", which is not actually correct based on the meanings of those terms. (In this case the problem is probably made worse by the mental interpretation of "NP" as "Not Polynomial", when it really means "Nondeterministic machine can solve in Polynomial time", and if a deterministic machine can solve something in polynomial time, a nondeterministic machine can do so as well!)