# 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 elements to (N-i-1)th position.

Recurrence Relation   is the number of steps required to place the largest element at the end of the array and signifies that time required to sort the rest of 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 comparisons.

Recurrence Relation   is the time required to search the smallest element in the array and place it at the beginning of the array. is the time required to sort the rest of the 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  is the time required to sort elements. denotes the time required to insert the Nth element in the sorted sequence of 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  is the time required to sort the two equal parts of the array. 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 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  comparisons to find the pivot position and 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 elements. This happens if all the elements are either smaller or greater than the pivot element. ## 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 comparisons. We repeat until the heap is empty.

Recurrence Relation  is the number of comparisons required to delete/pop the top element from a heap and copy it somewhere else. is the time required to sort the rest of the elements using heapsort.