Setting up and solving recurrences

Simple linear recurrences

Example: Sum of items in list

An easy first example.

nat sum(List x)
{
   if (x.empty?)
      return 0
   else
      return x.first + sum(x.rest)
}

What is the appropriate size measure? — length of x.

T(n) = "steps" to compute sum(x), where n=|x|

T(n) = 1, if n=0
T(n) = 1 + T(n-1), if n>0

To solve, unroll into a summation: T(n) = &sum_i=0…n 1 = n+1 = O(n)

Example: Some similar sums

T(n) = 1, if n=0
T(n) = n + T(n-1), if n>0

To solve, unroll into a summation: T(n) = &sum_i=0…n i = n(n+1)/2 = O(n²)

T(n) = 1, if n=0
T(n) = 2n + T(n-1), if n>0

To solve, unroll into a summation: T(n) = &sum_i=0…n 2i = 2 &sum_i=0…n i = 2n(n+1)/2 = O(n²)

Example: Merge

List merge(List x, List y)
{
   if (x.empty?)
     return y
   if (x.first < y.first)
     return cons(x.first, merge(x.rest, y))
   else
     return cons(y.first, merge(x, y.rest))
}

First attempt at a recurrence:

T(m,n) = 1, if m=0
T(m,n) = 1 + max(T(m-1,n), T(m,n-1)), if m>0

A bit tricky to solve. (Although we could eventually find that T(m,n) = O(m+n), not surprisingly.)

For this and all other examples, could guess the closed form solution (or its bound), and prove the guess correct inductively. However, we're currently interested in finding such closed forms without guessing.

Second attempt: A unary T(n) would be easier to solve. Does it make sense here? What is appropriate measure of input size?

T(n) = 1, if n=0
T(n) ≤ 1 + T(n-1), if n>0

To solve, assume worst case, which then looks just like previous example.

When is this unrolling into a sum easy? General form:

T(n) = 1, n=k
T(n) = f(n) + T(n-c), n>k

Assuming the base case happens when n≤k, for some constant k, which is almost always the case, can simply omit writing the base case.

Divide-and-Conquer-style Recurrences

Example: Mergesort

List mergesort(List x)
{
   if (x.empty? or x.rest.empty?)
      return x
   else
      y,z = split x into halves
      return merge(mergesort(y), mergesort(z))
}

If |x| isn't a power of two, eventually get an uneven split. Let's temporarily ignore this.

T(n) = 1, if n=0 or n=1
T(n) = 2T(n/2) + 2n, if n>1

To solve…

Unroll recurrences equationally.

T(n)
= 2n + 2T(n/2)
= 2n + 2(2 n/2 + 2T(n/4))
= 2n + 2n + 4T(n/4)
= 2n + 2n + 4(2 n/4 + 2T(n/8))
= 2n + 2n + 2n + 8T(n/8)
= …
= 2n × #unrolls + 2^#unrolls × T(1)
= 2n × #unrolls + 2^#unrolls

How many times can we unroll? I.e., how many times can we divide n by 2? — log₂ n

T(n)
= 2n log₂ n + 2^{log₂ n}
= 2n log₂ n + n
= O(n log₂ n)

Unroll recurrences as a tree. (Same info, different format.)

                             T(n)

            T(n/2)                       T(n/2)
        =2(n/2)+2T(n/4)


                              ...


           T(2)       T(2)    ...    T(2)        T(2)
       =2(2)+2T(1)
       =8
          
       T(1)  T(1)   T(1) T(1) ... T(1) T(1)   T(1) T(1)
       =1

Prove inductively, T(n) ≤ C × (2n log n), for some C>0

Could have written the following

T(n) = 1, if n=0 or n=1
T(n) = 2T(n/2) + n, if n>1

Gives, within a constant factor, the same result.

What if n isn't a power of two?

T(n) = 1, if n=0 or n=1
T(n) = T(⌈n/2⌉) + T(⌊n/2⌋) + n, if n>0

Rather than solving directly, observe that more input never takes less time.

Could prove this inductively, but should be obvious.
Holds true for most recurrences about analyzing program resource usage.
Then T(n) ≤ T(nearest-power-of-2-bigger-than-n) = O(n²), so T(n) = O(n²).

This idea can be generalized. Rule of thumb: floors and ceilings in recurrences can usually be safely ignored.

Aside: `O`(`n` log `n`) vs. `O`(`n` log₂ `n`)

The logarithm base doesn't matter (if constant): O(log₂ n) = O(log₄ n) = O(log₁₀ n) = …

Need to prove this.

log_a n / log_b n = ? — log_a b — a constant

Asymptotes ignore constant factors, so can ignore constant bases.

Example: Binary Search

T(n) = 1, if n=0
T(n) = T(n/2) + 1, if n>0

Solve by unrolling.

Master Theorem (simplified version)

For f(n) = a⋅f(n/b) + c⋅n^d,

if a < b^d — f(n) = O(n^d)
if a = b^d — f(n) = O(n^d log n)
if a > b^d — f(n) = O(n^log_ba)

We're skipping the proof, but it follows our examples. Unroll the recurrences into a sum, and solve. Each case allows the sum to be bounded in a different way.

Apply to mergesort and binary search.

(The full Master Theorem generalizes the c⋅n^d part. See COMP 482 for the general form and proof.)

Other linear recurrences

Example: Breaking an n-digit password

T(n) = 1, if n=0
T(n) = 10 T(n-1), if n>0

Closed form: T(n) = 10ⁿ

Example: Fibonacci

F₀ = 0
F₁ = 1
F_n = F_n-2 + F_n-1, if n≥2

Previously, proved F_n = (aⁿ - bⁿ)/√5, where a = (1+√5)/2, b = (1-√5)/2, but how to derive that?

Try different initial conditions, and see how much series varies.

More generally…

Approach to recurrences of the form f(n) = b⋅f(n-1) + c⋅f(n-2):

Guess a sol'n of the form f(n)=αⁿ.

What is α? Well, we get α² - b⋅α - c = 0 (the characteristic polynomial).

(Note: If started with f(n-3) term, we'd have a cubic characteristic polynomial, etc.)
Compute solutions α₁, α₂ to the characteristic polynomial. Here, use the quadratic equation.

Verify these answers satisfy the recurrence, temporarily ignoring the initial conditions.
But what about the initial conditions? Hmm, don't work.

Sol'ns to the recurrence relation (w/o the initial conditions) are closed under (a) sums, (b) constant factors. If α₁ⁿ and α₂ⁿ are sol'ns, then so are j⋅α₁ⁿ + k⋅α₂ⁿ, for any j,k ∈ ℝ.

(That is, "a linear combo. of two sol'ns is also a sol'n", or equivalently, "the set of solutions form a vector space".)

Solve for j,k.
Are we done? Are there more solutions that aren't of the form αⁿ? At this point, we ask the mathematicians, and trust us when they give us the answer we want: yes, this is all solutions.

This technique generalizes:

Guess an exponential, get a polynomial of degree n,
Solve roots α₁, …, α_n.
A linear combination of those α's makes up all the possible answers.
Caveat: if α_i occurs with multiplicity m, then you also include α_iⁿ, n⋅α_iⁿ, n²⋅α_iⁿ, …, n^m⋅α_iⁿ.