Search code examples
time-complexitybig-ologarithm

What is the explanation of rewriting P=2^(logN) as log2(P) = log2(N)?


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:

graph of log2(2^log(x)) and log2(x)

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.


Solution

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