# 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 + 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`. 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 + 1 By proof above ≤ n2 + 2n + 1 = (n+1)2
5. Thus, we can conclude that the running time of `isort` is O(n2).