Recurrence Relation for Sorting Algorithms

In this article, we will study recurrence relation for different sorting algorithms.

Recurrence Relation for Bubble Sort

Pseudo Code For Bubble Sort

for( i=0 ; i<N-1 ; ++i ){
	for( j=0 ; j<N-i-1 ; ++j){
                if( array[i] > array[j] )
                        swap( array[i] , array[j] );
        }
}

For each iteration of the outer loop, we place the largest element at the end of the array. In simple words, the ith iteration of the outer loop move the largest element from the first $N-i$ elements to (N-i-1)th position.

Recurrence Relation
$T(N) = T(N-1) + N-1$
$T(N) = T(N-1) + N\;(ignore\;constant)$

$N$ is the number of steps required to place the largest element at the end of the array and $T(N-1)$ signifies that time required to sort the rest of $N-1$ elements.

Recurrence Relation for Selection Sort

In each iteration of selection sort, we search for the smallest element and place it at the beginning of the array. After that, we increment the beginning position of the array and again search for the smallest element among the rest of the elements and repeat.

Searching the smallest element in the array takes $N-1$ comparisons.

Recurrence Relation

$T(N) = T(N-1) + N - 1$
$T(N) = T(N-1) + N$

$N$ is the time required to search the smallest element in the array and place it at the beginning of the array. $T(N-1)$ is the time required to sort the rest of the $N-1$ elements.

Recurrence Relation for Insertion Sort

Insertion Sort Pseudo Code

i = 0
while i < N
	temp = array[i];
	j = i
        // inserting array[i] in the sorted sequence
	while j > 0 && array[j-1] > array[j]
		array[j] = array[j-1];
		j = j - 1;
	end while
	array[j] = temp;
end while

The ith iteration of the outer loop implies that we have sorted array till i – 1 index. We need to insert the ith element in the sorted elements in the range [0, i-1]. Since the size of the sorted portion is i, the insertion requires i – 1 comparison.

Recurrence Relation

$T(N) = T(N-1) + N$

$T(N-1)$ is the time required to sort $N-1$ elements. $N$ denotes the time required to insert the Nth element in the sorted sequence of $N-1$ elements.

Recurrence Relation for Merge Sort

Pseudo Code for Insertion Sort

function merge_sort(array, start, end)
	if(start<end)
		mid = (start + end)/2
		merge_sort(array,start,mid-1)
		merge_sort(array,mid+1,start)
		merge(array,start,end)
	end if
end function

On each call of merge_sort, we split the array into two equal parts. Then we recursively sort the two parts. After sorting the two halves, we merge them such that the array remains sorted.

Recurrence Relation

$T(N) = 2*T(N/2) + N$

$2*T(N/2)$ is the time required to sort the two equal parts of the array. $N$ is the time required to merge the two sorted parts into a single sorted array.

Recurrence Relation for Quick Sort

Pseudo Code for Quick Sort

function quick_sort(array, start, end)
	if(start<end)
		pivot = partition(array,start,end)
		quick_sort(array,start,mid-1)
		quick_sort(array,mid+1,start)
	end if
end function

Quicksort first chooses a random element X as the pivot and partition the array in 2 parts such that the elements smaller than X are on the left side and elements greater than X are on the right side. After partition, X is in the correct position. Then we recursively sort the elements on the left side X and elements on the right side of X.

The partition requires $N$ comparisons.

Recurrence Relation

Best Case
In the best-case scenario, the pivot will split the array into 2 equal parts. Therefore, the recurrence relation will be

$T(N) = 2*T(N/2) + N$

$N$ comparisons to find the pivot position and $2*T(N/2)$ to sort the two partitions of the array.

Worst Case
In the worst case, the pivot will split the array of size N such that one part will contain no element, and the other party will contain $N-1$ elements. This happens if all the elements are either smaller or greater than the pivot element.

$T(N) = T(N-1)+ N$

Recurrence Relation for Heap Sort

Suppose we have a min-heap. The top of the heap always points to the smallest element. We copy the top element of the heap to another array. After that, we delete/pop the top of the heap. The deletion requires $log(N)$ comparisons. We repeat until the heap is empty.

Recurrence Relation

$T(N) = T(N-1)+log(N)$

$log(N)$ is the number of comparisons required to delete/pop the top element from a heap and copy it somewhere else.
$T(N-1)$ is the time required to sort the rest of the elements using heapsort.