5.1 A First Recurrence: The Mergesort Algorithm

Divide and conquer algorithms are a class of algorithmic techniques in which one breaks the input into several parts, solves the problem in each part recursively,and then combines the solutions to these subproblems into an overall solution. Analyzing these problems usually involves solving recurrence relation that bounds the running time recursively in terms of the running time on smaller instances. Mergesort uses the same template as other divide and conquer algorithms to sort a given list of items:

• Break up problem of size n into two equal parts of size ½n
• Solve two parts recursively
• Combine two solutions into overall solution

So,let's T(n) denote the Mergesort's worst-case running times on input instances of size n.

• Supposing that n is even, the algorithm spends O(n) time to divide the input into two pieces of size n/2 each
• It then spends T(n/2) to solve each one since T(n/2) is the worst-case running time for an input of size n/2
• Finally, it spends O(n) time to combine the solutions from the 2 recursive calls
• Thus, the following recurrence relation is satisfied by the running time:
  • T(n) ≤ 2T(n/2) + cn for n >2
  • And T(2) ≤ c

T(n/2) + T