Analysis of Recursive Algorithms

General Plan

1. Choose your parameter n (input size)
2. Identify the basic operation.
3. Check if work varies by input.
   • If it doesn’t vary, we only analyze once.
   • If it varies, we have to analyze bext/worst/average separately.
4. Set up recurrence relation
   • Express how much work algorithm does in terms of smaller problems.
5. Solve the recurrence (or, at the very least, establish its solution’s order of growth) by backward substitution¹1. Repeatedly substituting the recursive definition into itself until a pattern emerges that can be evaluated as a summation. or another method.

Note — More on Step 4:

\text{Format: } T(n) = \text{[work for recursive calls] + [work done at current level]}

Also, don’t forget to define the initial condition.

Example: Factorial

Q: Find the order of growth of this recursive function.

ALGORITHM F(n)
    // Computes n! recursively
    // Input: A nonnegative integer n
    // Output: The value of n!
    if n = 0 return 1
    else return F(n-1) \large{*} n

Definition

Factorial: n! = 1 \times 2 \times \dots \times (n-1) n \forall n \ge 1 and 0 \ne 1

A:

Step 1: Parameter n

Step 2: Basic operation is multiplication.

Step 3: Work is same for all inputs of size n

Step 4: Set up recurrence:

\begin{aligned} F(n) &= F(n-1) \times n \text{ for } n \ge 1 \text{ and} \\ F(0) &= 1 \end{aligned}

We want to count number of basic operations, so we can express this as:

M(n) = M(n-1) + 1 \text{ for } n > 0 \\~\\

Initial condition: M(0) = 0

Note — M(n-1) multiplications are spent computing F(n-1). One more multiplication is needed to multiply the result by n²2. Hence +1.

Step 5: Solve recurrence

Now, we can do backwards substitution (solve M and plug it into itself to discover the pattern):

\begin{aligned} M(n) &= M(n-1) + 1 \\ &= [ M(n-2) + 1 ] + 1 = M(n-2) + 2 \\ &= [ M(n-3) + 1 ] + 2 = M(n-3) + 3 \end{aligned}

Thus:

M(n)=M(n-i)+i= \dots =M(n-n)+n=n

Thus, the time efficiency of this algorithm is O(n).

Example: Tower of Hanoi

Tower of Hanoi: Move n disks from peg A to peg C using peg B as auxiliary.

• Only 1 disk can be moved at a time, and a larger disk cannot be placed on top of a smaller one.
• Initially, all disks are on peg A in order of size (largest on bottom)

Recursive Strategy:

1. Move top n-1 disks from A to B³3. using C as auxiliary
2. Move the largest disk from A to C
3. Move n-1 disks from B to C (using A as auxiliary)

Q: Find the order of growth.

A:

Step 1. n is # of disks.

Step 2. Basic operation: Moving one disk.

Step 3. Work is the same for all inputs of size n.

Step 4. Set up recurrence:

M(n) = 2M(n-1) + 1 \\ M(1)=1

Step 5. Backwards substitution

\begin{aligned} M(n) &= 2M(n-1) + 1 \\ &= 2[2M(n-2) + 1] + 1 = 2^2 M(n-2) + 2^1 + 2^0 \\ &= 2^2 [2M(n-3) + 1] + 2^1 + 2^0 = 2^3 M(n-3) + 2^2 + 2^1 + 2^0 \\ &\dots \\ &= 2^i M(n-i) + (2^i - 1) \end{aligned}

When i = n-1:

M(n) = 2^{n-1} \times M(1) + (2^{n-1} - 1) = 2^{n-1} \times 1 + 2^{n-1} - 1 = 2^n - 1

Thus, time complexity is O(2^n).

Example: Fibonacci Numbers

Recurrence:

F(n) = F(n-1) + F(n-2)\\ F(0) = 0\\ F(1) = 1

This creates a tree of recursive calls with massive overlap.

F(5) calls F(4) and F(3)
F(4) calls F(3) and F(2)
F(3) calls F(2) and F(1)
et cetera

There isn’t a simple closed form to solve for, so this one is currently out of our reach. We’ll cover this again in a later chapter (dynamic programming) to see how to avoid this massive overlap.