We did an introduction to big-O plus an inductive proof of a claim involving an inequality.
The inequality claim was that 2^n grows more quickly than n^2. We proved this by showing that the ratio of n2 divided by 2n is less than (3/4)n-5, for any n >= 5. A key lemma used in the inductive step is that (n+1)2 < (3/2) n^2 (as long as n >= 5).
We walked through some examples of algorithms analysis:
A pages with demos of different sorting algorithms, including mergesort: