0
$\begingroup$

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 <= 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$
  • $\begingroup$ Your question doesn't seem to be about algorithms or even Landau notation, but about basic mathematics. Are you sure you are in the right place and don't want to be on Mathematics? $\endgroup$ – Raphael May 11 '20 at 6:46
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't understand at all. "You may have come across logarithmic equations"… What is that? $\endgroup$ – Garrett May 12 '20 at 7:10
  • $\begingroup$ Oh, I just found: youtube.com/watch?v=fnhFneOz6n8 This is difficult and very new for me. I can almost understand… But how is it related to this algorithm… $\endgroup$ – Garrett May 18 '20 at 5:54
  • $\begingroup$ log2(64) = 6 | As, 64 = 2^6 (base 2). Base 2? 2^6 = 64 and that's base 10. In base 2, 2^6 = 1000000. So I'm confused again… When you say base 2, you mean the subscript 2 after the word log. I don't get it. What is this? $\endgroup$ – Garrett May 18 '20 at 6:02
  • $\begingroup$ Where can I find a tutor to help me study this? $\endgroup$ – Garrett May 20 '20 at 18:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.