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.