arrays - insertion sort theoretical analysis, total number of shifts. -

given following array:

[14 17 21 34 47 19 71 22 29 41 8] 

and following excerpt book algorithms unlocked thomas cormen (slightly edited, [start] , [stop] flags not part of text):

insertion sort excellent choice when array starts out ''almost sorted''. [start] suppose each array element starts out within k positions of ends in sorted array. total number of times given element shifted on iterations of inner loop @ k. therefore, total number of times elements shifted on inner-loop iterations, @ kn, in turn tells total number of inner-loop iterations @ kn (since each inner-loop iteration shifts 1 element 1 position).[stop] if k constant, total running time of insertion sort Θ(n), because Θ-notation subsumes constant factor k. in fact can tolerate elements moving long distance in array, long there not many such elements. in particular, if l elements can move anywhere in array (so each of these elements can move n-1 positions), , remaining n - l elements can more @ k positions, the total number of shifts is @ l * (n – 1) + (n – l) * k = (k + l) * n – (k + 1) * l, Θ(n) if both k , l constants.

the books trying explain how crafts formula, presents @ bottom of text. better understand says, likely, specific example using above sample array, going on k , n variables. can me better understand above excerpt's analysis?

to more specific confusing me, lines between [start] , [stop] flags ,these lines:

suppose each array element..... in turn tells total number of inner-loop iterations @ kn(since each inner-loop iteration shifts 1 element 1 position).

(anything below these lines totally understood way end.)

let consider insertion sort algorithm

algorithm: insertionsort(a)

i ← 1 while < length(a)     j ←     while j > 0 , a[j-1] > a[j]         swap a[j] , a[j-1]         j ← j - 1     end while     ← + 1 end while 

the inner loop - move elements of a[0..i-1] 1 one, till a[i] in correct position. therefore if given element atmost k position away correct place, have maximum of k compares , swaps. n elements k*n.

hope helps!