Hacker Newsnew | comments | ask | jobs | submitlogin
geoffschmidt 325 days ago | link | parent

Well, it's like this -- log_2 and log_10 (and natural log) differ only by a constant multiplicative factor, so they're all the same asymptotically, and it doesn't matter which one you use inside the O(). Pretty neat right?

eieio 325 days ago | link

Yes, you can convert log base x to log base y. However, the point is that if OP is assuming that we're using log base 10, developing an intuitive understanding of why a binary search is O(log n) is significantly harder than if OP knows that we're referring to log base 2.


valleyer 325 days ago | link

This is correct, but in case it makes more sense this way (it does to me):

log (base X) Y === log (base e) Y / log (base e) X

So the difference between log (base 2) and log (base 10) is just the difference between being divided by log (base e) 2 or log (base e) 10. Since those are both constant factors, big-O notation doesn’t care.


tsahyt 325 days ago | link

It's actually the same statement after all just with and without the actual math. But yes, it's very easy to see it from this.


wavesounds 325 days ago | link

Yeah totally for the purposes of big O theory its super neat. But before you can do big O you need to be able to actually calculate the number of steps a function takes to complete. If your a student trying to figure this out for the first time and you want to divide and conquer a list of 8 elements you do 3 operations, thus you get log_2 8 = 3 or log_2 (n) = # of operations. This is then generalized in big O notation but I think trying to do big O before being able to calculate steps for an example function is putting the cart before horse.


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