Hacker News Reader

Comment by wavesounds | Hacker News Reader

Did anyone make sure this guy knows that log in Computer Science is base 2? We need to remember that most places simply writing 'log' is assumed to be base 10.

Log base 2 is just how many times we can you recursively split something in half, which is not that complicated of a concept. However, his log example is base 10 and if he was trying to figure out these things as base 10 it would be super confusing and not make any sense.

View on HN

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?

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.

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.

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.

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.

For what it's worth, when I started studying this stuff I assumed log(n) meant log_e(n). That didn't help much either.

Reply on news.ycombinator.com