Example: insertion sort

//a[0, .. n-1] is an array

for (i=1; i<n; i++)

insert a[i] into the already sorted array

a[0,...,i-1]

Invariant: a[0,i-1] is sorted

Recurrence : T(n) ? T(n-1) + c1

T(1) = c2

Previous slide

Next slide

Back to first slide

View graphic version