CODEWITHSUNDEEP
algorithmsortingtime-complexitymergesortrecurrence
user1767754
user1767754

Reputation: 25094

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

Upvotes: 1

Views: 1640

Answers (1)

Ahmed Gamal
Ahmed Gamal

Reputation: 1696

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

Upvotes: 3

Related Questions