# Prove by induction that the recurrence form of bubble sort is $\Omega(n^2)$

The recurrence form of bubble sort is $$T(n)=T(n-1)+ n- 1$$

How can I prove by induction that this is $$\Omega(n^2)$$?

I'm stuck with $$T(n+1) \geq cn^2 + n = n(cn+1)$$

## 1 Answer

Assuming $$T(1)=1$$, you can show by induction that $$T(n) = \frac{n(n-1)}{2} + 1$$.

The base case is trivial since $$T(1) = 1 = \frac{1 \cdot 0}{2} + 1$$.

As for the inductive step, suppose that the claim holds up to $$T(n)$$. \begin{align*} T(n+1) &= T(n) + (n+1) - 1 =\frac{n(n-1)}{2} + 1 + n \\ &= \frac{n^2 -n +2n}{2} + 1 = \frac{n^2 + n}{2} + 1 = \frac{n(n+1)}{2} + 1 \\ &= \frac{(n+1)((n+1) - 1)}{2} + 1. \end{align*}

• So, all I need to do is to choose the scalar? I wondered if it's ok to do, it seems so but I wasn't sure. Thanks again! – Combinatoric May 17 at 14:33