Recursive Algorithm Analysis

• L’Hopital’s rule
  If $\lim_{n \to\infty} f(n) = \lim_{n\to \infty} g(n) = \infty$ and the derivatives f′ and g′ exist, then

$\lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} \frac{f'(n)}{g'(n)}$

• Stirling’s formula
  $n! \approx \sqrt{2 \pi n}(\frac{n}{e})^n$
  where e is the base of natural logarithm, $e \approx 2.718$. $\pi \approx 3.1415$

---

A recurrence relation is an equation that recursively defines a sequence of values given some initial terms.

Reviewish Examples:

• Fibonacci Sequence
  $(0, 1, 1, 2, 3, 5, 8, ...)$

  • $a_n = a_{n-1} + a_{n-2}$ for $n \geq 2$
    $a_0 = 0$
    $a_1 = 1$

• Geometric Progression
  $(3, 6, 12, 24, 48, ...)$ Find a recurrence relation!

  • $a_n = 2a_{n-1}$ for $n \geq 1$
    $a_0 = 3$

  • But how do we find out what $a_{667}$?

    • We want a formula to solve this
    • $a_n = ?$
    • $a_n = 3(2^n)$

  • if $a_n = da_{n-1}$ where $a_0 = k$ then $a_n = k(d^n)$

  Geometric Progressions: suppose some relation $a_n = da_{n-1}$ and $a_0 = k$ for some constant $d$ and $n \geq 1$ then $a_n = k(d^n)$ for $n \geq 0$

• Another sequence
  $(0, 2, 6, 12, 20, 30, 42, ...)$

  • ($a_1 - a_0 = 2$)
    ($a_2 - a_1 = 4$)
    ($a_3 - a_2 = 6$)
    ...
    +($a_n - a_{n-1} = 2n$)
    --
    $a_n - a_0 = 2 + 4 + 6 + 8 + ... + 2n$
    $= 2(1 + 2 + ... + n)$
    $= 2 \sum_{i = 1}^{n} i$
    $= 2(\frac{n(n+1)}{2})$
    $= n(n+1)$
    So, $a_n - a_0 = n(n+1)$
    $a_n = n(n+1)$

  • Check if it works!

    • $a_6 = 6(6+1) = 42$

  • If $a_n - a_{n-1} = k$ and $a_0 = c$ for $n \geq 1$ then $a_n = c + \sum_{i=1}^n k$

    • Applied to example: $a_n = 0 + \sum_{i=1}^n 2n = 2 \sum_{i=1}^n n = \frac{2(n)(n+1)}{2} = n(n+1)$

---

Example: Find $n!$
NonRecursiveFindFactorial(n):

result = 1
for i <- 1 ... n
result = result * i
return result

Recurrence: f(n) = n * f(n - 1)

RecursiveRecursiveFindFactorial(n):
if n = 0
return 1
else
return n * RecursiveFindFactorial(n - 1)

Analysis of Recursive Algorithms (3 methods):

1. Iteration Method

• Expand (iterate) the recurrence and express it as a summation of terms depending only on $n$ and the initial conditions.

Example: $n!$
$T(n) = T(n-1) + 1$

$T(n) = T(n - 1) + 1$
$= (T(n - 2) + 1) + 1$
$= T(n - 2) + 2$
...
$= T(n - i) + i$
...
$= T(0) + n = \mathcal{O} (n)$

2. Substitution Method
   Example:
   Let $T(1) = 4$
   $T(n) = 2T(\frac{n}{2}) + 4n$

Build solution by substituting scratch work	Scratch pad
$T(n) = 2T(\frac{n}{2}) + 4n$	$T(\frac{n}{2} = 2T(\frac{n}{2^2}) + 4(\frac{n}{2})$
$= 2[ 2T(\frac{n}{2^2}) + 4\frac{n}{2}] + 4n$ $= 2^2 T(\frac{n}{2^2}) + 4n + 4n$	$T(\frac{n}{2^2}) = 2T(\frac{n}{2^3} + 4(\frac{n}{2^2}))$
$= 2^2 [2T(\frac{n}{2^3}) + 4 \frac{n}{2^2}] + 4n + 4n$ $= 2^3 T(\frac{n}{n^3}) + 4n + 4n + 4n$	Pattern?? $T(\frac{n}{2^3}) = 2T(\frac{n}{2^4})+ 4(\frac{n}{2^3})$
$= 2^3[2T(\frac{n}{2^4})+ 4(\frac{n}{2^3})] + 4n + 4n + 4n$ $= 2^4 T(\frac{n}{2^4}) + 4n + 4n + 4n + 4n$
$= 2^i T(\frac{n}{2^i}) + i(4n)$	We need to get to the base case: $\frac{n}{2^i} = 1$ i.e. $n = 2^i$ $\to \log_2 n = i$
Substitute into equation above: $2^{\log_2 n} T(1) + (\log_2 n) (4n)$ $=n(4) + 4n \log_2 n$ $=4n + 4n \log_2 n \in \mathcal{O}(n\log_2 n)$	$T(1) = 4$ and $2^{\log_2 n} = n ^{\log_2 2} = n^1 = n$

3. Master Theorem

• We'll see this next week when we take a look at chapter 5.1

Useful Recurrence Types:
Linear: One (constant) operation reduces problem size by one.

• $T(n) = T(n-1) + c$
• $T(1) = d$
• Solution: $T(n) = (n-1)c + d$

Quadratic: A pass through input reduces problem size by one.

• $T(n) = T(n-1) + cn$
• $T(1) = d$
• Solution: $T(n) = [\frac{n(n+1)}{2} – 1] c + d$

Logarithmic: One (constant) operation reduces problem size by half.

• $T(n) = T(n/2) + c$
• $T(1) = d$
• Solution: $T(n) = c log n + d$

n log n: A pass through input reduces problem size by half.

• $T(n) = 2T(n/2) + cn$
• $T(1) = d$
• Solution: $T(n) = cn \log n + d n$