Introduction

Loop Variant

Insert Sort: Loop Variant

• Initialization

• Maintenance

• Termination

Running Time

Insertion Sort: Running Time

Big-O Notation

• $O(g(n))$ is a set of functions, all functions that do not grow faster than g(n).

• O() gives an upper bound on a function.

• n = $O(n^2)$

• 2n = $O(n)$ $\mathrm{\exists }c,n,\mathrm{\forall }n>n_0:2n<=c\ast n$

• n = $O(2n-4)$ $\mathrm{\forall }n>4,n<=2n-4$

Prove $n^2\notin O(nlogn)$

Assume that $\mathrm{\forall }n>=n_0,n^2<=nlogn$

Big-$\omega$ Notation

• Ω(g(n)) is a set of functions all functions that do not grow slower than g(n).