CS312 Recitation 11
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 + 1

    By Induction Hypothesis

  5. Thus, we can conclude that the running time of insert is O(n).

Now, we need the recurrence relation for isort'and a bound on that recurrence. The proof of the bound on this recurrence relation will use the relation we have for our function insert. However, since isort' is a function of two arguments, the recurrence relation will also be a function of two arguments, where the first argument, m, is the length of the first list l1 and the second argument, n, is the length of the second list l2.


T(0,n) = c1

T(m,n) = T(m-1,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 m >= 0, the T(m,n) <=1 + mn + m2/2 where m and n are as defined above. Proof by induction on m.

  2. Base Case: m = 0: T(0,n) = 1 <= 1 + 0(n) + 02/2

  3. Induction Hypothesis: Assume that for arbitrary m, T(m,n) ≤ 1 + mn + m2/2.

  4. Prove T(m+1,n) ≤ 1 + (m+1)n + (m+1)2/2.

    T(m+1, n)

    =

    T(m, n+1) + Tinsert(n)

     

    ≤

    1+ m(n+1) + m2/2 + Tinsert(n)

    By Induction Hypothesis

     

    ≤

    1+ m(n+1) + m2/2 + n

    By proof above

     

    =

    1+ mn+m + m2/2 + n

     

    =

    1+ mn + n + (m2 + 2m)/2

     

    <=

    1+ (m + 1)n + (m2 + 2m + 1)/2

     

    =

    1+ (m + 1)n + (m2 + 1)2/2

  5. Thus, we can conclude that the running time of isort' is O(mn + m2).


  1. Now, we can prove the runtime of isort directly by using the runtime of isort'. isort(l) = isort'(l,[]). We proved that the runtime of isort' is O(mn + m2) where m is the length of the first argument and n is the length of the second argument. Since the length of the second argument in the call to isort' is 0, the runtime of isort is O(m2).


Derivation of recurrence bound for isort'

Here is an outline of the derivation of the bound for the recurrence relation for isort'.


T(m, n)

=

T(m, n+1) + Tinsert(n)


 

≤

T(m-1, n+1) + n

By proof above

 

=

T(m-2, n+2) + (n+1) + n

Expanding the recurrence once

 

=

T(m-2, n+3) + (n+2) + (n+1) + n


 

=

T(0, n+m) + (n+m-1) + ... + (n+2) + (n+1) + n

Expanding the recurrence m times

 

=

1 + (n+m-1) + ... + (n+2) + (n+1) + n

Substituting for T(0,n+m)

 

=

1 + [(n+m-1) + ... + 1] – [(n-1) + (n-2) + ... + 1]

Extending the summation


=

1 + (n+m-1)(n+m)/2 – (n-1)n/2

sum(i) for 1 <= i <= k is k(k+1)/2


<=

1 + mn + m2/2