# 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) = c*_{1} |

*T(n) = T(n-1) + c*_{2} |

We will assume that both *c*_{1} and *c*_{2}
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:

**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*
**Base Case**: *n = 1*: *T(1) = 1*
**Induction Hypothesis**: Assume that for arbitrary *n*,
*T(n) ≤ n*
**Prove ***T(n+1) ≤ n+1*
*T(n+1)* | *=* | *T(n) +
1* |

| ≤ | *n + 1* | By Induction
Hypothesis |

- 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) = c*_{1} |

*T(n) = T(n-1) + T*_{insert}(n) |

We will again assume that both *c*_{1} is *1*. We will now prove the running time using induction:

**Claim**: For all *n > 0*, the running time of
`isort(l)`

is quadratic, i.e., *T(n) ≤ n*^{2}, where
the length of `l`

is *n*. Proof by induction on
*n*
**Base Case**: *n = 1*: *T(1) = 1*
**Induction Hypothesis**: Assume that for arbitrary *n*,
*T(n) ≤ n*^{2}
**Prove ***T(n+1) ≤ (n+1)*^{2}
*T(n+1)* | *=* | *T(n) +
T*_{insert}(n) |

| ≤ | *n*^{2} + T_{insert}(n+1) | By Induction
Hypothesis |

| ≤ | *n*^{2} + n +
1 | By proof above |

| ≤ | *n*^{2} + 2n +
1 |

| = | *(n+1)*^{2} |

- Thus, we can conclude that the running time of
`isort`

is *O(n*^{2}).