Hacker Newsnew | comments | ask | jobs | submitlogin
dllthomas 348 days ago | link | parent

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 348 days ago | link

> 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).

-----

crossroads091 348 days ago | link

What was the second answer?

-----

bastijn 348 days ago | link

2 and the "no need for base in big-O" makes 2 :).

-----

saraid216 348 days ago | link

Maybe they wanted both answers?

-----




Lists | RSS | Bookmarklet | Guidelines | FAQ | DMCA | News News | Feature Requests | Bugs | Y Combinator | Apply | Library

Search: