05.md

title
Analyzing Recursive Algorithms

Analysis of Recursive Algorithms

General Plan

1. Choose your parameter $n$ (input size)
2. Identify the [basic operation]{.underline}.
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]{.underline}
   • 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]{.underline} 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) * 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.