stillAFanOfTheSimpsons stillAFanOfTheSimpsons - 14 days ago 7
Java Question

Time complexity for a sorting algorithm

I came across the following question while I was doing some exercise:


A sorting algorithm starts from start of the list, scan until two succeeding items that are in the wrong order are found. Swap those items and go back to the beginning. The algorithm ends when the end of the list is reached.

What is the worst-case running time for a list of size n?


I feel that it is similar with bubble sort, but probably worse that that because it doesn't finish the whole pass of scanning the list. But I can't figure out how to calculate its time complexity. I am not sure if the code I came up below for this algorithm is correct. Many thanks for your help!

for (int i=0, i<n , i++){//n is the size of the array
if (array[i]>array[i+1]){
swap (array[i], array[i+1]);
i=0;
}
}

Answer

The number of comparisons for the worst case (I wont prove the worst case is n, n-1, ... 1 but I assume it is) is a tetrahedral number.

Why?

imagine a sequence

n, n-1, .... 1

so for 1, will be swap when everything before is already on place. So the number of comparisons when is in the last place will be n-1 before is swapped to the second last place. From the second last place it will have to do n - 2 comparisons. Following this logic, and extending to the previous numbers we have for different n:

In other words, for position n i will need to move one number down (1), from position n - 1 I will need to move 2, (1 & 2), from n-2 (1, 2 & 3). Assuming 1,2,3... n is the valid order and they start as n,...3, 2,1.

n = 3 -> 2 + 1 * 2 = 4 
n = 4 -> 3 + 2 * 2 + 3= 10 
n = 5 -> 4 + 3 * 2 + 2 * 3 + 4 = 20 
n = 6 -> 5 + 4 * 2 + 3 * 3 * 2 * 4 + 5 = 35
n = 7 -> 6 + 5 * 2 + 4 * 3 + 3 * 4 + 2 * 5 + 6 = 56 
n = 8 -> 7 + 6 * 2 + 5 * 3 + 4 * 4 + 3 * 5 + 2 * 6 + 7= 84

And this sequence is the tetrahedral numbers.

The formula for the n-th tetrahedral number is represented by the 3rd rising factorial of n divided by the factorial of 3

And as a binomial coeficient:

binomial coeficient

So, it seems that it is O(n^3)

Comments