Good morning,

I implemented the Binary Insertion Sort algorithm in C++, and now I want to analyse its time complexity. This is the Insertion Sort algorithm, but the linear search technique (which is used for locating the position in which to insert a particular integer) is replaced by a binary search technique.

I will try to do a detailed analysis of the number of comparisons made by the algorithm during its runtime. I should point out that this is for self-study purposes. I am posting it in this forum because I want to know if my reasoning is correct, if there are any inconsistencies or mistakes. This is a very long post, so I will appreciate if you take your time and have enough patience to analyse it carefully. I tried to be as clear as possible, but also to make the analysis succint (in order not to make this post longer than it could be). I wrote some mathematical expressions here in a formatted way, to try to make it easier to read.

The algorithm is the following:

The variableCode:`#include <iostream>`

#include <cmath>

using namespace std;

int main() {

int list[] = {3, 1, 4, 888, 999, 45, 3};

int n = 7;

int m;

for (int j = 1; j < n; j++) { //list[j] is the jth integer of the list

int i = 0;

int left, right, m, s;

//binary search

left = 0;

right = j;

while (left < right) {

m = floor((left + right)/2);

if (list[j] > list[m]) left = m + 1; else right = m;

}

i = left; //i is the index of the new position of list[j]

s = list[j]; //save list[j]

//swap

if (i != j){

for (int k = 0; k <= j - i - 1; k++){

list[j-k] = list[j-k-1];}

list[i] = s;

}

}

return 0;

}

listis a vector of ints withnelements that need to be sorted (in this case,n= 7, and the list has elements arbitrarily chosen).

There is an outer loop through the list (withjranging from 1 ton- 1). Inside this outer loop, there are two loops: awhileloop for the binary search (which serves to search for the position in which to place thejth element) and aforloop (to swap the positions of the integers and place thejth integer in the correct position).

First, I will start by analysing the complexity of the binary search portion, in terms of comparisons made. Then, I will analyse the complexity of the code that swaps the integers.

Binary search portion

In each iteration of the outer loop, the binary search will be applied to a list containing the elements 0 toj. That is, a list containingj+ 1 elements.

I will simplify the analysis by splitting it in two cases: 1) the number of elements in the list (j+ 1) is a power of 2 and 2)j+ 1 is not a power of two.

First case

In the first case, I will express the number of elements as j+1=2^{k}, wherekis a positive integer andk= log_{2}(j+1).

In thewhileloop of the binary search, the number of elements in the list will be successively divided by 2 until it is equal to 1. Thus, in this case, because the number of elements is 2^{k}, there will bekiterations of thewhileloop.

In each iteration of this loop, two comparisons are made: one to enter the loop (to verify whetherleft<right) and one inside the loop (to verify iflist[j]>list[m]). That gives 2kcomparisons for all iterations. But there is still one more comparison in order to leave the loop (when it is verified thatleft=right). That gives a total of 2k+ 1=2log (j+1)+1 comparisons.

As one binary search will be performed for each iteration of the outer loop, this number of comparisons will be repeated withj= 1, 2, 3, ...,n-1. Therefore, the total number of comparisons of the binary search will be the sum with j going from 1 to (n - 1) of:

2log (j+ 1) + 1

Which I could represent in summation notation as:

n-1

Σ [2log (j+ 1) + 1]

j=1

If I distribute the summation, it becomes:

2(log 2 + log 3 +... + logn) +n- 1 = 2log (n!) +n- 1

But 2logn! +n- 1 is O(n log n). Therefore, the time complexity of this binary search portion is O(nlogn).

Second case

In the second case, where the number of elements on which to perform the binary search is not a power of two, I will increase the number of elements in the list to 2^{k+1}, wherek=floor(log_{2}(j+1)), to make it a power of two and thus simplify the calculations.

This case is much similar to the first case. The number of elements in the list will also be successively divided by 2 until it is equal to 1. Then, as there are 2^{k+1}items in the list, the number of iterations of the loop will bek+1 (it was onlykin the other case). As there are two comparisons for each iteration plus one to leave the loop, there will be 2(k+1)+1=2k+3=2*floor(log_{2}(j+1))+3.

As before, the search will be repeated withj= 1, 2, 3, ...,n-1. Thus:

n-1

Σ [2*floor(log_{2}(j+1))+3]

j=1

which is less or equal than:

n-1

Σ [2*log_{2}(j+1)+3]=2logn!+3(n-1)

j=1

which is also O(nlogn). Then, just like the other case, the complexity will also be O(nlogn).

I should point out now that the number of comparisons of the binary search in this algorithm is always O(nlogn); there is no worst or best case scenario.

Portion that swaps the integers

I am referring to theifstatement (ifi!=j) with aforloop inside, below the comment line that says "//swap".

This loop depends on the variablei, which indicates the new position in which to insert thejth integer.

I will consider two cases: best case scenario and worst case scenario.

The best case is when the list is already sorted (that is, it is in non-increasing order). If that's so,iwill always equalj(because the position of the integer doesn't need to be changed). Thus, theforloop will only verify ifi!=j, and then it will stop (becauseiwill always equalj, as I said). Because this comparison is performed withj= 1, 2, 3, ...,n-1, (n- 1) comparisons will be performed, and, thus, the complexity of the swap will be O(n).

The worst case is when the list is in strictly decreasing order. In that case,iwill always equal zero (because eachjth integer will need to be swapped to the beginning of the list). Thus, theforloop will be performed fromk= 0 tok=j-1. Thus,jiterations of this loop will be performed. As there is one comparison in the loop (which verifies whetherk<=j-i- 1), there will bejcomparisons for eachjwithj= 1, 2, 3, ...,n-1. Of course, I will have to add one more comparison (needed to leave the loop) and the (n- 1) comparisons performed by theifclause (that also appeared in the best case). The total of comparisons due to the loop will be:

n+ Σj= (n-1)n/2 +n

where the summation goes fromj= 1 to (n- 1)

(the "n" that I added is because of the comparison needed to leave the loop and the (n- 1) comparisons by theifclause:n- 1 + 1 =n). Thus, in this case, the number of comparisons of the swapping code is O(n²).

Conclusion

The complexity of the binary search is O(nlogn).

The swap, on the other hand, has complexity O(n) on the best case and O(n²) on the worst case.

Thus, in the best case of the Binary Insertion Sort as a whole, its total number of comparisons is O(nlogn) (becausenlognof the binary search grows faster thannof the swap), and, in the worst case, its total number of comparisons is O(n²) (becausen² of the swap grows faster thannlognof the binary search).

I should remark that, in the number of comparisons of this algorithm, I didn't include the comparisons performed by the outer loop (the verifications of whetherj<nof the outerforloop), but it wouldn't make difference for the big O estimate.

Thank you in advance.