I'm working through the Big-O chapter of Cracking the Coding Interview, and can't wrap my head around one of the manipulations of logarithms that is suggested.
Page 50 of the book tries to show that O(2log N)
is equivalent to O(N)
.
The book starts with Let P = 2log N
, then it makes the claim: "By the definition of log2, we can write this as log2P = log2N"
That claim is where my understanding breaks down. I don't understand how you can reduce log2(2log N)
to log2(N)
. If you look at a graph of these two functions, they are clearly different:
This is a step in 'proving' that N = 2log N
- which also just seems like a false statement. If you graph them again, N
is a linear function, while 2log N
is a sublinear function.
Any beginner-friendly explanations for how this makes sense? Thanks!
Edit to show that log N
in this case means log-base-2(N):
In this example from the book, log N
represents the approximate depth of a balanced binary search tree. Just counting the first couple layers of a tree makes it clear that we are working with log-base-2:
Which log function gives us the answer "Given the number of nodes, what is the depth?" Clearly the answer is log-base-2. nodes depth log2(nodes) log10(nodes) 1 1 0 0 3 2 1.58 0.48 7 3 2.81 0.85 15 4 3.91 1.18 31 5 4.95 1.49 63 6 5.98 1.80
@Kaiwen Chen's answer is spot-on. We're in the world of CS here and the assumed log base is 2. The book adds to this confusion because parts of the example reference an explicit log2
while the log N
to describe the depth of the tree is always written with an assumed base of 2.
In CS, a lot of log() functions are assumed to be base 2, so 2^(logx) = x. Your plotting visualization is assuming base 10.
This is a common problem software engineering students deal with. All math courses assume base e, all CS courses assume base 2, and all engineering courses assume base 10.