Average preformance of InsertionSort

Average number of comparisons while inserting (i+1)st element x to a sorted sequence

E[0]<E[1]<...<E[i-1]       ← x 

of i elements 


The algorithm

Try at index i:

          E[0]<E[1]< ...<E[i-1]<_      
                                                                       ↑?
                                                                   x

If yes then

              E[0]<E[1]<...<E[i-1]<x        

(done after 1 comparison) 

If no then try at index (i-1):

            E[0]<E[1]<...<E[i-2]<_<E[i] 
                                                                      ↑?
                                                                  x

If yes then


             E[0]<E[1]<...<E[i-2]<x<E[i]     

(done after 2 comps) 


If no then try at index (i-2):


            E[0]<E[1]<...<E[i-3]<_<E[i-1]<E[i] 
                                                                      ↑?
                                                                  x
If yes then


              E[0]<E[1]<...<E[i-3]<x<E[i-1]<E[i]     

(done after 3 comps) 


etc.

...

           E[0]<E[1]<...<E[j-1]<x<E[j+1]<...<E[i-1]<E[i]

(done after i-j+1 comps ; we will derive this formula below)

etc.

...

If no then try at index 1:

            E[0]<_<E[2]<...<E[i] 
                           ↑?
                       x

If yes then


             E[0]<x<E[2]<...<E[i]     

(done after i comps) 


If no then 

              x<E[1]<E[2]<...<E[i]     

(done after  how many comps?) 



Let 

• Pr(j) be the probability that the index of x after insertion in 

           E[0]<E[1]<...<E[j-1]<_<E[j+1]<...<E[i-1]<E[i]
                                                                  ↑ 
                                                                x
is j, where j ∈ {0,...,i}

• #comp(j) be the number of comparisons necessary for the program to determine that x should be inserted at index j


We have (assuming that all 
i+1 possible points of insertion are equally likely, see Figure 4.5 in your textbook):

		Pr(j) = (1/((i+1)))


When j gets decremented after each "no" in the above algorithm, #comp(j) gets incremented, except for the last step when #comps(1) = #comps(0) = i.

Hence, 

                 j + #comp(j) = constant 

for all 0 < j ≤ i. 

Putting j = i (the first step of the algorithm) yields 

                  i + 1 = constant

because #comps(i) = 1.

Therefore,for all 0 < j ≤ i, 

              j + #comp(j) = i + 1

or,(subtracting j from both sides)

              #comp(j) = i -j + 1.

So,

 # comp (j)=(Piecewise[{{i-j+1  for 0<j≤i
, 
}, {i       for j=0, 
}}])



The average number of comparisons while inserting (i+1)st element (where i ≥  0) is:

(∑_(j=0)^i)Pr(j)× #comp(j) = Pr(0)× #comp(0)+(∑_(j=1)^i)Pr(j)× #comp(j) =

(1/((i+1)))× i+(∑_(j=1)^i)(1/((i+1)))× (i - j + 1)

(i/2)+(i/(1+i))=(i/2)+((i+1)/(1+i))-(1/(1+i))=(i/2)+1-(1/(1+i))

Verification of the above

(i/2)+Factor[1-(1/(1+i))]

The average number of comparisons for all insertions is (remember that Pr(0)× #comp(0)=0 so the first insertion at i = 0 may be ignored):

(Subscript[T, avg])(n) =(∑_(i=1)^(n-1))(∑_(j=0)^i)Pr(j)× #comp(j)=
=(∑_(i=1)^(n-1))((i/2)+(i/(1+i))) =
=(∑_(i=1)^(n-1))((i/2)+1-(1/(i+1))) = (∑_(i=1)^(n-1))((i/2) + 1)- (∑_(i=1)^(n-1))(1/(1+i))

(∑_(i=1)^(n-1))(1/(1+i)) = (put j = i+1; j ∈ {2,...n})

=(∑_(j=2)^n)(1/j)= (∑_(j=1)^n)(1/j) - (1/1) =(∑_(j=1)^n)(1/j) -1.

So,
(Subscript[T, avg])(n) =(∑_(i=1)^(n-1))((i/2) + 1)- ((∑_(j=1)^n)(1/j) -1)=(∑_(i=1)^(n-1))((i/2) + 1)+1-(∑_(j=1)^n)(1/j).

(∑_(i=1)^(n-1))((i/2) + 1)+1

Expand[1+(1/4) (-4+3 n+(n^2))]

FullSimplify[((3 n)/4)+((n^2)/4)]

Thus (∑_(i=1)^(n-1))((i/2) + 1)+1=(1/4) n (n+3)

Thus 
(Subscript[T, avg])(n)=(1/4) n (3+n)-(∑_(j=1)^n)(1/j) 

Recall that 
(∑_(j=1)^n)(1/j)≈Log[n] + 0.577216

(Euler's formula for harmonic number, see file Summationa.nb)

Hence,

(Subscript[T, avg])(n) ≈(1/4) n (n+3) - Log[n]- 0.577216 =


-0.577216`+0.75` n+0.25` (n^2)- Log[n] ∈ Θ((n^2))

Note. The difference between (1/4) n (n+3) and textbook's lower bound for average number of comps (1/4) n (n-1) is   n.

Simplify[(1/4) n (n+3)-(1/4) n (n-1)]

n

Thus the difference between the upper bound and textbook's lower bound is

n-(∑_(j=1)^n)(1/j)≈n-(Log[n] + 0.577216)

Plot[Tooltip[{(1/4) n (n-1),(1/4) n (3+n)-Log[n]-0.577216`}],{n,1,20},PlotTheme->"Classic"]

Plot[Tooltip[{0.25`(n^2),(1/4) n (3+n),(1/4) n (3+n) - Log[n]- 0.577216}],{n,1,20}]

Limit[(1/(n^2))(-0.577216`+0.75` n+0.25` (n^2)-1.` Log[n]), n -> ∞]

Euler's formula, again:

Plot[{(∑_(j=1)^n)(1/j),Log[n]+ 0.577216},{n, 1,20}]

More accurate:

Plot[{(∑_(j=1)^n)(1/j),Log[n]+ 0.577216 +(1/(2n))},{n, 1,20}]

Even more accurate

Plot[{(∑_(j=1)^n)(1/j),Log[n]+ 0.577216 +(1/(2n))-(1/(12(n^2)))},{n, 1,20}]

They yield more precise (optional for all students) aproximation of the average number of comparisons

(Subscript[T, avg])(n) ≈(1/4) n (n+3) - Log[n]- 0.577216-(1/(2n))+(1/(12(n^2)))

Here is a visual verification of the above:

Plot[{(∑_(i=1)^(n-1))((i/2)+(i/(1+i))),(1/4) n (n+3)-(Log[n]+ 0.577216 +(1/(2n))-(1/(12(n^2))))},{n, 1,20}]

Plot[{(1/4) n (n-1),(∑_(i=1)^(n-1))((i/2)+(i/(1+i))),(1/4) n (n+3)-(Log[n]+0.577216` (+(1/(2 n)))-(1/(12 (n^2))))},{n,1,20},PlotTheme->"Classic"]