Big O Tires Question? My question is regarding the last paragraph of this excerpt from "Cracking the Coding Interview." (For some reason, my table is not formatting here.)

What's the runtime of this code?

int f(int n) {
  if (n &lt;= 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?
This requires some basic logarithm concepts. You may have come across logarithmic equations with general definition as:

logb(x) = y is valid if by = x | Here b is the base, y is the exponent value that makes by = x

Let's consider x having a value 64. Below are some logarithmic outputs (y) with different bases:

log2(64) = 6 | As, 64 = 26 (base 2)
log4(64) = 3 | As, 64 = 43 (base 4)
log8(64) = 2 | As, 64 = 82 (base 8)

If you notice above, the logs of different bases are only different by a constant factor. (between 6, 3 and 2)
Now let's consider no change in base and this time we will consider exponential base, a general expression would be something like:

loge(x) = y , or ln(x) = y

Let's consider x having value 2n. So y will be:

y = loge(2n), or y = ln(2n)

Now if we change value of x to 8n then y would be:

y = loge(8n) = loge(23n)

23n can be represented in terms of 2n as:

23n = 22n * 2n (or 23*n or 2n * 2n * 2n)

If you notice, the difference between x being 2n and x being 23n is not by any constant factor.
Hence validating the statement:

The base of an exponent does matter. Compare 2^n and 8^n. If you expand 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.