CS312 Recitation 12
Proving Running Times With Induction

Solving recurrences inductively

You have already seen how an asymptotic analysis can give us some indications on how efficient a procedure runs. Starting from a recurrence relation, we want to come up with a closed-form solution, and derive the run-time complexity from the solution. Remember that you have to prove your closed-form solution using induction. 

A slightly different approach is to derive an upper bound (instead of a closed-formula), and prove that upper bound using induction.

Proving the running time of insertion sort

Recall the code you saw for insertion sort:

fun insert(e:int, l:int list):int list =
  case l of
     [] => [e]
   | x::xs => if (e < x) then e::l else x::(insert (e,xs))

fun isort' (l1: int list, l2:int list) =
   case l1 of
     [] => l2
   | x::xs => isort'(xs, insert(x, l2))

fun isort(l:int list) = isort'(l, [])

First, we want to prove that the running time of insert is O(n). First, let us consider the recurrence relation:

T(1) = c1
T(n) = T(n-1) + c2

We will assume that both c1 and c2 are 1. It is safe to do so since different values of these constants will not change the asymptotic complexity of T (think, for instance, that the corresponding machine operations take one single time step). We will now prove the running time using induction:

  1. Claim: For all n > 0, the running time of insert(e,l) is linear, i.e., T(n) ≤ n, where the length of l is n. Proof by induction on n
  2. Base Case: n = 1: T(1) = 1
  3. Induction Hypothesis: Assume that for arbitrary n, T(n) ≤ n
  4. Prove T(n+1) ≤ n+1
    T(n+1)=T(n) + 1
     ≤n + 1By Induction Hypothesis
  5. Thus, we can conclude that the running time of insert is O(n).

Now, we need the recurrence relation for isort. This will be use the relation we have for our funciton insert
T(1) = c1
T(n) = T(n-1) + Tinsert(n)

We will again assume that both c1 is 1. We will now prove the running time using induction:

  1. Claim: For all n > 0, the running time of isort(l) is quadratic, i.e., T(n) ≤ n2, where the length of l is n. Proof by induction on n
  2. Base Case: n = 1: T(1) = 1
  3. Induction Hypothesis: Assume that for arbitrary n, T(n) ≤ n2
  4. Prove T(n+1) ≤ (n+1)2
    T(n+1)=T(n) + Tinsert(n)
     ≤n2 + Tinsert(n+1)By Induction Hypothesis
     ≤n2 + n + 1By proof above
     ≤n2 + 2n + 1
     =(n+1)2
  5. Thus, we can conclude that the running time of isort is O(n2).