2 ms·
I was asked the O() of binary search. I said "log n". They asked "what base?" ... obviously they wanted 2, but O() doesn't work that way - changing base is a
by dllthomas 14y ago
I was asked the O() of binary search. I said "log n". They asked "what base?"
... obviously they wanted 2, but O() doesn't work that way - changing base is a constant factor. Sometimes there's a tension between figuring out someone's understanding of the algorithm and someone's understanding of the notation (and math behind it). Of course, I gave them both answers...
- ot 14y ago> changing base is a constant factor. Only if the base is constant. For example B-trees have O(log_B n)-time operations, and you can't ignore the B because it is a parameter (hence non-constant).
- saraid216 14y agoMaybe they wanted both answers?
- crossroads091 14y agoWhat was the second answer?
- bastijn 14y ago2 and the "no need for base in big-O" makes 2 :).