Question

What is the recurrence relation for merge sort algorithm? Compute the time complexity of

merge sort using recursion tree method.

Answer 1

The recurrence relation for merge sort is T(n) = 2T(n/2) + O(n), denoting recursive sorting of two sublists and their merging. Using the recursion tree method shows that merge sort has a time complexity of O(n log n), with log(n) levels in the recursion tree and O(n) work at each level.

Step-by-step explanation:

The recurrence relation for the merge sort algorithm takes into account the divide and conquer strategy that merge sort employs. Merge sort divides the input list into two halves, sorts the two halves recursively, and then merges them back into a sorted list. The recurrence relation can be expressed as:

T(n) = 2T(n/2) + O(n)

Here, T(n) is the time complexity of merge sort for a list of size n, 2T(n/2) represents the time to sort the two halves of the list recursively, and O(n) is the time to merge the two sorted halves.

Using the recursion tree method to find the time complexity involves creating a tree where each level represents a recursive call to merge sort, and the time to merge at each level is noted. The tree has log(n) levels since the list is halved at each recursive step. The total work done at each level of the tree is O(n), as the merging at each level involves looking at each of the n elements. Therefore, the time complexity of merge sort is the sum of work done across all log(n) levels, leading to a final time complexity of:

O(n log n)