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 or another method.

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: n! = 1 \times 2 \times ... \times (n-1) n \forall n \ge 1 \text{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 operatios, so we can express this as:

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

• M(n-1) multiplications are spent computing F(n-1)
• One more multiplication is needed to multiply the result by n (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-1)+1=...=M(n-i++i=...=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 (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: You know the drill.

A:

Step 1. n is # of disks.

Step 2. Basic operation: Moving on disk

Step 3.

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 \\ &... \\ &= 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} × 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, this was just to illustrate the limits of this general approach.