next up previous index CD Book Algorithms
Next: Lecture 4 - heapsort Up: No Title Previous: Lecture 2 - asymptotic

Lecture 3 - recurrence relations

Listen To Part 3-1

Problem 2.1-2: Show that for any real constants a and b, b > 0,  


To show tex2html_wrap_inline13580 , we must show O and tex2html_wrap_inline13582 . Go back to the definition!

Note the need for absolute values.

Listen To Part 3-2

Problem 2.1-4:

(a) Is tex2html_wrap_inline13606 ?

(b) Is tex2html_wrap_inline13608 ?

(a) Is tex2html_wrap_inline13610 ?

Is tex2html_wrap_inline13612 ?

Yes, if tex2html_wrap_inline13614 for all n

(b) Is tex2html_wrap_inline13616

Is tex2html_wrap_inline13618 ?

note tex2html_wrap_inline13620

Is tex2html_wrap_inline13622 ?

Is tex2html_wrap_inline13624 ?

No! Certainly for any constant c we can find an n such that this is not true.

Listen To Part 3-3

Recurrence Relations

Many algorithms, particularly divide and conquer algorithms, have time complexities which are naturally modeled by recurrence relations.  

A recurrence relation is an equation which is defined in terms of itself.

Why are recurrences good things?

  1. Many natural functions are easily expressed as recurrences:




  2. It is often easy to find a recurrence as the solution of a counting problem. Solving the recurrence can be done for many special cases as we will see, although it is somewhat of an art.

Listen To Part 3-4

Recursion is Mathematical Induction!

In both, we have general and boundary conditions, with the general condition breaking the problem into smaller and smaller pieces.   

The initial or boundary condition terminate the recursion.  

As we will see, induction provides a useful tool to solve recurrences - guess a solution and prove it by induction.


n 0 1 2 3 4 5 6 7
tex2html_wrap_inline13626 0 1 3 7 15 31 63 127

Guess what the solution is?

Prove tex2html_wrap_inline13628 by induction:

  1. Show that the basis is true: tex2html_wrap_inline13630 .
  2. Now assume true for tex2html_wrap_inline13632 .
  3. Using this assumption show:


Listen To Part 3-5

Solving Recurrences

No general procedure for solving recurrence relations is known, which is why it is an art. My approach is:  

Realize that linear, finite history, constant coefficient recurrences always can be solved

Check out any combinatorics or differential equations book for a procedure.

Consider tex2html_wrap_inline13634 , tex2html_wrap_inline13636 , tex2html_wrap_inline13638

It has history = 2, degree = 1, and coefficients of 2 and 1. Thus it can be solved mechanically! Proceed:


Systems like Mathematica and Maple have packages for doing this.   

Listen To Part 3-6

Guess a solution and prove by induction

To guess the solution, play around with small values for insight.

Note that you can do inductive proofs with the big-O's notations - just be sure you use it right.  

Example: tex2html_wrap_inline13640 .

Show that tex2html_wrap_inline13642 for large enough c and n. Assume that it is true for n/2, then


Starting with basis cases T(2)=4, T(3)=5, lets us complete the proof for tex2html_wrap_inline13650 .

Listen To Part 3-7

Try backsubstituting until you know what is going on

Also known as the iteration method. Plug the recurrence back into itself until you see a pattern.  

Example: tex2html_wrap_inline13652 .

Try backsubstituting:


The tex2html_wrap_inline13654 term should now be obvious.

Although there are only tex2html_wrap_inline13656 terms before we get to T(1), it doesn't hurt to sum them all since this is a fast growing geometric series:



Listen To Part 3-8

Recursion Trees

Drawing a picture of the backsubstitution process gives you a idea of what is going on.  

We must keep track of two things - (1) the size of the remaining argument to the recurrence, and (2) the additive stuff to be accumulated during this call.

Example: tex2html_wrap_inline13660

tex2html_wrap13800 tex2html_wrap13802
The remaining arguments are on the left, the additive terms on the right.

Although this tree has height tex2html_wrap_inline13662 , the total sum at each level decreases geometrically, so:


The recursion tree framework made this much easier to see than with algebraic backsubstitution.

Listen To Part 3-9

See if you can use the Master theorem to provide an instant asymptotic solution

The Master Theorem:   Let tex2html_wrap_inline13664 and b>1 be constants, let f(n) be a function, and let T(n) be defined on the nonnegative integers by the recurrence


where we interpret n/b as tex2html_wrap_inline13674 or tex2html_wrap_inline13676 . Then T(n) can be bounded asymptotically as follows:

  1. If tex2html_wrap_inline13680 for some constant tex2html_wrap_inline13682 , then tex2html_wrap_inline13684 .
  2. If tex2html_wrap_inline13686 , then tex2html_wrap_inline13688 .
  3. If tex2html_wrap_inline13690 for some constant tex2html_wrap_inline13692 , and if tex2html_wrap_inline13694 for some constant c<1, and all sufficiently large n, then tex2html_wrap_inline13698 .

Listen To Part 3-10

Examples of the Master Theorem

Which case of the Master Theorem applies?

Listen To Part 3-11

Why should the Master Theorem be true?

Consider T(n) = a T(n/b) + f(n).

Suppose f(n) is small enough

Say f(n)=0, ie. T(n) = a T(n/b).

Then we have a recursion tree where the only contribution is at the leaves.  

There will be tex2html_wrap_inline13756 levels, with tex2html_wrap_inline13758 leaves at level l.


so long as f(n) is small enough that it is dwarfed by this, we have case 1 of the Master Theorem!

Listen To Part 3-12

Suppose f(n) is large enough

If we draw the recursion tree for T(n) = a T(n/b) + f(n).

If f(n) is a big enough function, the one top call can be bigger than the sum of all the little calls.

Example: tex2html_wrap_inline13766 . In fact this holds unless tex2html_wrap_inline13768 !

In case 3 of the Master Theorem, the additive term dominates.

In case 2, both parts contribute equally, which is why the log pops up. It is (usually) what we want to have happen in a divide and conquer algorithm.

Listen To Part 3-13

Famous Algorithms and their Recurrence

Matrix Multiplication

The standard matrix multiplication algorithm for two tex2html_wrap_inline13770 matrices is tex2html_wrap_inline13772 .    

tex2html_wrap13808 tex2html_wrap13810
Strassen discovered a divide-and-conquer algorithm which takes tex2html_wrap_inline13774 time.

Since tex2html_wrap_inline13776 dwarfs tex2html_wrap_inline13778 , case 1 of the master theorem applies and tex2html_wrap_inline13780 .

This has been ``improved'' by more and more complicated recurrences until the current best in tex2html_wrap_inline13782 .

Listen To Part 3-14

Polygon Triangulation

Given a polygon in the plane, add diagonals so that each face is a triangle None of the diagonals are allowed to cross.   

tex2html_wrap13812 tex2html_wrap13814
Triangulation is an important first step in many geometric algorithms.

The simplest algorithm might be to try each pair of points and check if they see each other. If so, add the diagonal and recur on both halves, for a total of tex2html_wrap_inline13784 .

However, Chazelle gave an algorithm which runs in tex2html_wrap_inline13786 time. Since tex2html_wrap_inline13788 , by case 1 of the Master Theorem, Chazelle's algorithm is linear, ie. T(n) = O(n).


The classic divide and conquer recurrence is Mergesort's T(n) = 2 T(n/2) + O(n), which divides the data into equal-sized halves and spends linear time merging the halves after they are sorted.  

Since tex2html_wrap_inline13794 but not tex2html_wrap_inline13796 , Case 2 of the Master Theorem applies and tex2html_wrap_inline13798 .

In case 2, the divide and merge steps balance out perfectly, as we usually hope for from a divide-and-conquer algorithm.

Mergesort Animations

Approaches to Algorithms Design


Job is partly done - do a little more, repeat until done.  

A good example of this approach is insertion sort


A recursive technique  

A good example of this approach is Mergesort.

next up previous index CD Book Algorithms
Next: Lecture 4 - heapsort Up: No Title Previous: Lecture 2 - asymptotic

Mon Jun 2 09:21:39 EDT 1997