Search code examples
algorithmsortingtime-complexitymergesortrecurrence

Recurrence of Merge-Sort - need explanation

This is the recurrence of the worst-case running time T(n) of the Merge-Sort procedure.

What is T?

why 2T(n/2) ?

For which operation is the O(n) ?

enter image description here

Solution

  • For simplicity, assume that n is a power of 2 so that each divide step yields two subproblems, both of size exactly n/2.

    The base case occurs when n = 1.

    When n ≥ 2, time for merge sort steps:

    Divide: Just compute q as the average of p and r, which takes constant time i.e. Θ(1).

    why 2T(n/2) ?

    Conquer: Recursively solve 2 subproblems, each of size n/2, which is 2T(n/2).

    enter image description here

    For which operation is the O(n) ?

    Combine: MERGE on an n-element subarray takes Θ(n) time.

    Summed together they give a function that is linear in n, which is Θ(n). Therefore, the recurrence for merge sort running time is

    enter image description here