The Algorithm Design Manual Second Edition

43

2.5.2

Insertion Sort

A basic rule of thumb in Big Oh analysis is that worst-case running time follows

from multiplying the largest number of times each nested loop can iterate. Consider

the insertion sort algorithm presented on page

4,

whose inner loops are repeated

here:

for (i=1; i

j=i;

while ((j>0) && (s[j] < s[j-1])) {

swap(&s[j],&s[j-1]);

j = j-1;

}

}

How often does the inner while loop iterate? This is tricky because there are

two different stopping conditions: one to prevent us from running off the bounds

of the array (j > 0) and the other to mark when the element finds its proper place

in sorted order (s[j] < s[j

− 1]). Since worst-case analysis seeks an upper bound

on the running time, we ignore the early termination and assume that this loop

always goes around i times. In fact, we can assume it always goes around n times

since i < n. Since the outer loop goes around n times, insertion sort must be a

quadratic-time algorithm, i.e. O(n

2

).

This crude “round it up” analysis always does the job, in that the Big Oh

running time bound you get will always be correct. Occasionally, it might be too

generous, meaning the actual worst case time might be of a lower order than implied

by such analysis. Still, I strongly encourage this kind of reasoning as a basis for

simple algorithm analysis.