So this is the Master theorem for Merge Sort:

$$ T(n) = 2T(n/2) + \Theta(n). $$

I am not able to understand why is the time complexity for sorting and merging $\Theta(n)$.

Is sorting $O(1)$ and merging $O(n)$?

  • 3
    $\begingroup$ No, that is not the "Master's theorem" for merge sort; that is simply its time complexity expressed as a recursion which can be asymptotically approximated using the master theorem (no capital and no apostrophe; "master" is not someone's name). $\endgroup$ – dkaeae Feb 20 '19 at 9:50
  • 1
    $\begingroup$ Also, if you mean $\Theta(n)$ (instead of $\theta(n)$), merging takes worst-case linear steps since, in the worst-case, you merge 2 lists of (approximately) $\frac{n}{2}$ elements each. $\endgroup$ – dkaeae Feb 20 '19 at 9:51

Each iteration of merge sort consist of 2 phases:

  1. Merge Sorting the first and the second half separately.
  2. Merging the two halves.

So in your equation phase 1 is represented by $2T(n/2)$. This means that merge sort is called on the two halves. This is a recursive call, which is why $T$ is used here.

Phase 2 is represented by $\Theta(n)$. Merging two lists of length $a$ and length $b$ takes $\Theta(a+b)$. In our case the two lists are both of size $\frac{1}{2}n$, so we get a total of $\Theta(n)$.

In the end we get that $T(n) = $ step 1 + step 2, resulting in $T(n) = 2T(n/2) + \Theta(n)$

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.