Recurrence Relations

CS F364 — Design & Analysis of Algorithms | Summer 2026

Substitution method, Master theorem, two-variable recurrences

Problem 1

Solve the recurrence relation of the Tower of Hanoi problem using the iterative method.

Solution

Let T(n) be the number of moves required to transfer n disks from source to destination using an auxiliary peg.

Recurrence: T(n) = 2T(n-1) + 1, with T(0) = 0.

Iterative expansion: \begin{aligned} T(n) &= 2T(n-1) + 1 \\ &= 2[2T(n-2) + 1] + 1 = 2^2 T(n-2) + 2 + 1 \\ &= 2^2[2T(n-3) + 1] + 2 + 1 = 2^3 T(n-3) + 4 + 2 + 1 \\ &\;\;\vdots \\ &= 2^n T(0) + (2^{n-1} + 2^{n-2} + \dots + 2 + 1) \\ &= 0 + (2^n - 1). \end{aligned} Thus T(n) = 2^n - 1 = \Theta(2^n).

Problem 2

How many ones does the following procedure print when run with input n? Compute the best bounds you can: the exact value if possible, a \Theta expression if you can’t find the exact value, or O and \Omega bounds if you can’t find a \Theta expression.

Ones(n):
    if n = 0:
        print 1
    else:
        for i = 1 to 2^n:
            Ones(n-1)

Solution

Let T(n) be the number of ones printed on input n.

From the code: T(0) = 1,\qquad T(n) = 2^n \cdot T(n-1) \quad \text{for } n \ge 1. Iterating: \begin{aligned} T(n) &= 2^n \cdot 2^{n-1} \cdots 2^1 \cdot T(0) \\ &= 2^{n + (n-1) + \dots + 1} \cdot 1 \\ &= 2^{n(n+1)/2}. \end{aligned} Hence T(n) = 2^{n(n+1)/2}. This is \Theta\!\left(2^{n(n+1)/2}\right), which is 2^{\Theta(n^2)} but not \Theta(2^{n^2}).

Problem 3

Solve the following recurrence using the substitution method:

T(n) = 2T(\lfloor n/2 \rfloor + 17) + n

Solution

We guess T(n) = O(n\log n), i.e., T(n) \le cn\log_2 n for n \ge n_0.

Assume the inequality holds for all k < n. For n large enough (n \ge 68), \lfloor n/2 \rfloor + 17 \le 3n/4.

Then: \begin{aligned} T(n) &\le 2c\!\left(\frac{3n}{4}\right)\!\log_2\!\left(\frac{3n}{4}\right) + n \\ &= \frac{3c}{2}\,n\,(\log_2 n + \log_2 3 - 2) + n \\ &= \frac{3c}{2}\,n\log_2 n + \frac{3c}{2}\,n\,(\log_2 3 - 2) + n. \end{aligned} For this to be \le cn\log_2 n, we need: \frac{3c}{2}\,n\log_2 n + \frac{3c}{2}\,n\,(\log_2 3 - 2) + n \le cn\log_2 n. Simplifying: \dfrac{3c}{2}(\log_2 3 - 2) + 1 \le \dfrac{c}{2}\log_2 n.

Choosing c and n_0 appropriately (e.g., c \ge 2, n_0 = 2^{c+1}) satisfies the inequality. Thus T(n) = O(n\log n). A matching lower bound \Omega(n\log n) follows similarly, so T(n) = \Theta(n\log n).

Problem 4

Solve each recurrence to get the best asymptotic bounds on T(n):

T(n) = T\!\left(\dfrac{n}{4\log_2 n}\right) + 2n for n > 1, T(1) = 1 (you may assume all numbers round down to the nearest integer). You may use the Master theorem.
T(n) \le T(\lceil n/2\rceil) + T(\lfloor n/2\rfloor) + cn\log n for n \ge 4, T(2) = 2. Do not use the Master theorem.

Solution

(i) Lower bound: The 2n term alone gives T(n) = \Omega(n).

Upper bound: For n > 1, 4\log_2 n > 4, so \dfrac{n}{4\log_2 n} < \dfrac{n}{4}. Hence: T(n) \le T\!\left(\frac{n}{4}\right) + 2n. By the Master theorem with a=1, b=4, f(n)=2n: \log_b a = \log_4 1 = 0. Since f(n) = 2n = \Omega(n^{\log_4 1 + \epsilon}) for \epsilon = 1, case 3 applies: T(n) = O(n). Together with the lower bound, T(n) = \Theta(n).

(ii) We prove T(n) \le cn\log^2 n by induction.

Base: T(2) = 2 \le c\cdot 2\log^2 2 = 2c, true for c \ge 1.

Inductive step: For n \ge 4, \begin{aligned} T(n) &\le T\!\left(\lceil n/2\rceil\right) + T\!\left(\lfloor n/2\rfloor\right) + cn\log n \\ &\le c\lceil n/2\rceil \log^2\!\left(\lceil n/2\rceil\right) + c\lfloor n/2\rfloor \log^2\!\left(\lfloor n/2\rfloor\right) + cn\log n \\ &\le cn\log^2\!\left(n/2\right) + cn\log n \quad\text{(since both halves $\le n/2$)} \\ &= cn(\log n - 1)^2 + cn\log n \\ &= cn(\log^2 n - 2\log n + 1) + cn\log n \\ &= cn\log^2 n - cn\log n + cn \\ &\le cn\log^2 n \quad\text{for $n \ge 2$}. \end{aligned} Thus T(n) = O(n\log^2 n). One can similarly show \Omega(n\log^2 n), so T(n) = \Theta(n\log^2 n).

Problem 5

Prove the asymptotic complexity for each two-variable recurrence, where T(n,n) is the runtime:

Prove T(n,n) = \Theta(n):

T(x,y) = \Theta(x) if y \le 2

T(x,y) = \Theta(y) if x \le 2

T(x,y) = \Theta(x+y) + T(x/2,\,y/2) otherwise

Prove T(n,n) = \Theta(n\log n):

T(x,y) = \Theta(x) if y \le 2

T(x,y) = \Theta(y) if x \le 2

T(x,y) = \Theta(x) + T(x,\,y/2) otherwise

Solution

(i) Unrolling the recurrence: \begin{aligned} T(x,y) &= c(x+y) + T\!\left(\frac{x}{2},\frac{y}{2}\right) \\ &= c(x+y) + c\!\left(\frac{x+y}{2}\right) + T\!\left(\frac{x}{4},\frac{y}{4}\right) \\ &\;\;\vdots \\ &= c(x+y)\!\left(1 + \frac12 + \frac14 + \dots\right) \\ &\le 2c(x+y). \end{aligned} The lower bound is T(x,y) \ge c(x+y) from the first term. Hence T(x,y) = \Theta(x+y), and T(n,n) = \Theta(n).

(ii) Unrolling: \begin{aligned} T(x,y) &= cx + T\!\left(x,\frac{y}{2}\right) \\ &= cx + cx + T\!\left(x,\frac{y}{4}\right) \\ &\;\;\vdots \\ &= cx \cdot (\log_2 y) + \Theta(x) \quad\text{(base case when $y \le 2$)}. \end{aligned} Thus T(x,y) = \Theta(x\log y), and T(n,n) = \Theta(n\log n).