Hacker Newsnew | comments | ask | jobs | submitlogin
fatemayasmine 354 days ago | link | parent

Often the followup question to what is the O notation of X is why? So if you are just going to memorize the cheat sheet then it won't get you very far.

It is good to know what you should know about though.

dllthomas 354 days ago | link

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

What was the second answer?


bastijn 354 days ago | link

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


saraid216 354 days ago | link

Maybe they wanted both answers?


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