0
$\begingroup$

My question is regarding the last paragraph of this excerpt from "Cracking the Coding Interview."

What's the runtime of this code?

int f(int n) {
  if (n <= 1) {
    return 1;
  }
  return f(n -1) + f(n -1);
}

The tree will have depth N. Each node (i.e., function call) has two children. Therefore, each level will have twice as many calls as the one above it. The number of nodes on each level is:

Level #Nodes Also expressed as… Or… 0 1 20 1 2 2 * previous level = 2 2^1 2 4 2 * previous level = 2 * 2^1 = 2^2 2^2 3 8 2 * previous level = 2 * 2^2 = 2^3 2^3 4 16 2 * previous level = 2 * 2^3 = 2^4 2^4

Therefore, there are 2^0 + 2^1 + 2^2 + 2^3 + 2^4 + 2^N (which is 2^n+1 - 1) nodes. (see "Sum of powers of 2 on page 630.)

Try to remember this pattern. When you have a recursive function that makes multiple calls, the runtime will often (but not always) look like O(branches^depth), where branches is the number of times each recursive call branches. In this case 2, so O(2^n).

As you may recall, the base of a log doesn't matter for big O since logs of different bases are only different by a constant factor. Howerver, this does not apply to exponents. The base of an exponent does matter. Compare 2^n and 8^n. If you expant 8^n, you get (2^3)^n, which equals 2^3n, which equals 2^3n * 2^n. As you can see, 8^n and 2^n are different by a factor of 2^2n. That is very much not a constant factor.


I do not understand the last paragraph. What base of a log? What is that and why do they say this here? What do they mean?

$\endgroup$
0