Self-Assessment Quiz: Solving Recurrence Relations

Twenty questions to check your understanding of divide-and-conquer recurrences, the recursion tree, the Master Theorem, merge sort and binary search, and Fibonacci by matrix exponentiation. Answer before opening the key. Aim for 16+.

Question 1

In the divide-and-conquer recurrence $T(n) = a\,T(n/b) + f(n)$, the constant $a$ is:

A) the factor by which the input shrinks B) the number of recursive calls actually made (the branching factor) C) the non-recursive work D) the height of the recursion tree

Question 2

For $T(n) = 8\,T(n/2) + n^2$, the critical exponent $E = \log_b a$ is:

A) $1$ B) $2$ C) $3$ D) $\log_2 8 = 3$, and both C and this are the same

Question 3

The recursion tree for $T(n) = a\,T(n/b) + f(n)$ has height:

A) $\log_a n$ B) $\log_b n$ C) $n/b$ D) $a^{\log_b n}$

Question 4

The number of leaves in that recursion tree equals:

A) $a \cdot b$ B) $\log_b n$ C) $a^{\log_b n} = n^{\log_b a}$ D) $f(n)$

Question 5

Merge sort's recurrence $T(n) = 2\,T(n/2) + \Theta(n)$ falls into which Master-Theorem case, and why?

A) Case 1, because $f(n)$ is polynomially smaller than $n^E$ B) Case 2, because $f(n) = \Theta(n) = \Theta(n^E)$ with $E = 1$ C) Case 3, because $f(n)$ is polynomially larger than $n^E$ D) None — the Master Theorem doesn't apply

Question 6

Binary search's recurrence is $T(n) = T(n/2) + \Theta(1)$. Its solution is:

A) $\Theta(1)$ B) $\Theta(\log n)$ C) $\Theta(n)$ D) $\Theta(n \log n)$

Question 7

Why does binary search have $a = 1$ while merge sort has $a = 2$, even though both halve the input?

A) Binary search is iterative; merge sort is recursive B) Binary search recurses on only one half (throwing the other away); merge sort sorts both halves C) Merge sort halves twice per step D) It is a convention with no real meaning

Question 8

In Master-Theorem Case 3, beyond "$f(n)$ is polynomially larger than $n^E$," you must also verify:

A) the base case is $\Theta(1)$ B) $a$ and $b$ are integers C) the regularity condition $a\,f(n/b) \le c\,f(n)$ for some constant $c < 1$ D) that $f(n)$ is a polynomial

Question 9

For $T(n) = 2\,T(n/2) + n^2$ (Case 3), the solution is:

A) $\Theta(n)$ B) $\Theta(n \log n)$ C) $\Theta(n^2)$ D) $\Theta(n^2 \log n)$

Question 10

The Master Theorem says nothing about $T(n) = 2\,T(n/2) + n\log n$ because:

A) $a$ is not an integer B) the gap between $f(n) = n\log n$ and $n^E = n$ is only logarithmic, not polynomial C) $f(n)$ is smaller than $n^E$ D) the recurrence has no solution

Question 11

The naive recursive Fibonacci runs in time:

A) $\Theta(n)$ B) $\Theta(n \log n)$ C) $\Theta(\phi^n)$, exponential D) $\Theta(\log n)$

Question 12

Why is the naive Fibonacci recurrence $T(n) = T(n-1) + T(n-2) + \Theta(1)$ not solvable by the Master Theorem?

A) It has two subproblems B) The subproblems shrink by subtraction ($n-1$), not division ($n/b$) C) $f(n)$ is constant D) It actually is solvable by the Master Theorem

Question 13

The matrix $M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ satisfies $M^n = \begin{pmatrix} F_{n+1} & F_n \ F_n & F_{n-1} \end{pmatrix}$. To read off $F_n$ from $M^n$, you take the:

A) determinant B) top-left entry, $F_{n+1}$ C) top-right (or bottom-left) entry, $F_n$ D) trace

Question 14

Computing $F_n$ by matrix exponentiation takes $O(\log n)$ multiplications because:

A) matrix multiplication is fast B) exponentiation by squaring halves the exponent each step, so $\Theta(\log n)$ steps suffice C) Fibonacci numbers grow slowly D) the matrix is only $2 \times 2$

Question 15

The recurrence governing exponentiation by squaring (on the exponent $n$) is:

A) $T(n) = 2\,T(n/2) + \Theta(n)$ B) $T(n) = T(n/2) + \Theta(1)$ — the same as binary search C) $T(n) = T(n-1) + \Theta(1)$ D) $T(n) = n\,T(n-1)$

Question 16 (True/False, justify)

True or false: Binet's closed form $F_n = \frac{\phi^n - \psi^n}{\sqrt 5}$ is the best way to compute $F_n$ exactly for very large $n$. Justify in one sentence.

Question 17 (True/False, justify)

True or false: Merge sort's $\Theta(n\log n)$ bound holds in the best, worst, and average case alike. Justify in one sentence.

Question 18 (True/False, justify)

True or false: "$f(n)$ is larger than $n^E$" is enough to conclude Master-Theorem Case 3. Justify.

Question 19 (Short answer)

State the three-step strategy for applying the Master Theorem to a recurrence $T(n) = a\,T(n/b) + f(n)$.

Question 20 (Short answer)

In one sentence each, name the right tool for: (a) a subtractive recurrence like $T(n) = T(n-1) + \Theta(n)$; (b) a recurrence with *unequal* subproblem sizes like $T(n) = T(n/3) + T(2n/3) + \Theta(n)$.

Answer Key

Topics to review by question