Question

Find a big-O estimate for the worst-case complexity in terms of number of comparisons used and the number of terms swapped by the binary insertion sort described in the preamble to Exercise$47$ in Section$3.1$ .

Short answer

O(n log n).

Step-by-step solution

Step 1

Result previous exercise:

Procedure: binary insertion sort $(a_1,a_2,...a_n:integerswithn\ge 1)$

for$k:=2ton$

$$\begin{gathered} i:=1 \\ j:=k \end{gathered}$$

while i < j

$$\begin{gathered} m:=\lfloor (i+j)/2\rfloor \\ if{a}_k>a_{m}theni:=m+1elsej:=m \end{gathered}$$

if $a_k\le a_i$then

$temp:=a_k$

for$p:=0tok-i-1$

$$\begin{gathered} a_{k-p}:=a_{k-p-1} \\ {a}_i:=temp \end{gathered}$$

return $a_1,a_2,...a_n$.

Step 2

SOLUTION

The algorithm makes 2 comparison in each iteration of the while-loop and makes 1 additional comparisons for each iteration of the for-loop.

The number of iterations of the while-loop is the number of times we divide the sub list of k integers into 2 lists. If$k=2^m$, then this means that the while-loop has$m=lo{g}_{2}k$iterations. If$2^{m-1}<k<2^m$, then the while-loop has iterations. Since $\lceil lo{g}_{2}k\rceil$when $lo{g}_{2}k$is an integer, there are $\lceil m\rceil =\lceil lo{g}_{2}k\rceil$iterations of the while-loop.

The number of comparisons is the product of the number of iterations and the number of comparisons per iteration.

Number of comparisons in while-loop $=\sum _{k=2}^n \left(2⌈{\log }_{2}k⌉+1\right)$

$\begin{array}{c}=2\sum _{k=2}^n ⌈{\log }_{2}k⌉+(n-1)\\ \le 2\sum _{k=2}^n \left[{\log }_{2}n\right.⌉+(n-1)\\ =2(n-1)\left[{\log }_{2}n\right.⌉+(n-1)\\ =2n\left[{\log }_{2}n\right]-2\left.⌈{\log }_{2}n\right]+n-1\end{array}$

Thus at most $2n\lceil lo{g}_{2}n\rceil -2\lceil lo{g}_{2}n\rceil +n-1$comparisons are made and $2n\lceil lo{g}_{2}n\rceil -2\lceil lo{g}_{2}n\rceil +n-1$is $O(n\log n)$.