0
$\begingroup$

I was doing an exercise of time complexity of the algorithms that I've studied in class and there's something I don't understand.

The exercise says:

The best case of the merge operation in MergeSort Algorithm is

(a) Constant

(b) Lineal

(c) Quadratic

(d) None of the above

So, I calculated the time complexity of the MergeSort algorithm. Since,

$$T(n)=2T(n/2)+cn$$ $$T(n/2)=2T(n/4)+c\frac{n}{2}$$ $$T(n/4)=2T(n/8)+c\frac{n}{4}$$ $$...$$ where $T$ is the time that it takes for the algorithm to do all the calculations and $n$ the number elements in the array that we want to sort. I'm writing $2T(n/2)$ because we need to halve the array into two parts, and $cn$ because we need to merge these two parts later. Then, $$T(n)=8T(n/8)+3cn$$ Therefore, $$T(n)=2^{k}T(n/2^{k})+kcn$$ But I want to express everything with respect to $n$, so since dividing the number of elements $n$ by 2 $k$ times gives us 1 element of the array, then: $$1=\frac{n}{2^{k}}$$ So, $$k=\log_{2}{n}$$ Then, going back to the previous equation $$T(n)=(2^{\log_{2}{n}})T(n/2^{\log_{2}{n}})+cn(\log_{2}{n})=nT(1)+cn(\log_{2}{n})$$ Therefore, this means that the merge part is grows in this way: $cn(\log_{2}{n})$; and the halving part in this way: $nT(1)$. Then the answer should be d, right?

I'm not sure if I'm missing something here... Thank you.

$\endgroup$
2
  • 1
    $\begingroup$ The question is only asking about the merge step, why are you calculating the cost of the entire algorithm? $\endgroup$ Commented Jun 8, 2018 at 23:37
  • $\begingroup$ Well, I want to calculate the cost of the whole algorithm to see the cost of the merge part and the halving part. And I found that the merge part grows logarithmically, which doesn't make any sense. $\endgroup$
    – Arnau
    Commented Jun 9, 2018 at 7:21

1 Answer 1

1
$\begingroup$

Since the question is only asking what's the best case for just the merge operation, we only need to take into account the part of the algorithm where it "weaves" the two subarrays together. This subroutine runs in $O(n+m)$ where $n$ and $m$ are the lengths of the two subarrays. This is the case, because the individual subarrays are already sorted from the previous merge operation. So in summary, the merge operation runs in linear time.

Consider the following visual:

enter image description here

For demonstration sake, we will refer to the rows with elements as "array levels" and the rows with arrows as "merge levels". Between each pair of array levels is a merge level. In this case, $n=8$ (number of elements), and $k=3$ (number of merge levels). The $cn(\log_2n)$ part of your answer tells you that for each merge level, every single element is being merged. Even if the previous array level isn't merging into a single array in the next level, it's still being merged into some other array on the same level. For example, $[2, 10]$ and $[7,13]$ aren't being merged into the same array, but they're still being merged during the same "merge level". This means that regardless of $k$, every single element is still be merged. And since this happens $k$ times (or $\log_2n$ times in terms of $n$), the overall runtime of the algorithm is $n\log_2n$, which is what your calculations prove.

$\endgroup$
14
  • $\begingroup$ But I still don't understand. Why are my calculations not matching with this? I got that the merge part grows logarithmically, not linearly. $\endgroup$
    – Arnau
    Commented Jun 9, 2018 at 7:15
  • $\begingroup$ @Arnau The $cn(\log_2n)$ part of your answers tells you that all the elements ($n$) are merged $\log_2n$ times. Your explicit formula for $T(n)$ already assumes that the merge operation runs in linear time, because at each level, it has to ultimately merge $n$ elements. $\endgroup$
    – Badr B
    Commented Jun 9, 2018 at 8:17
  • $\begingroup$ I'm not sure I understand... Could you break it down a little bit? I'm sorry. $\endgroup$
    – Arnau
    Commented Jun 9, 2018 at 9:19
  • $\begingroup$ @Arnau I made an edit to my answer to help explain it more clearly. And don't be sorry! We're all here to learn. $\endgroup$
    – Badr B
    Commented Jun 9, 2018 at 9:53
  • $\begingroup$ Okay, then why is the answer (b) if it grows logarithmically? $\endgroup$
    – Arnau
    Commented Jun 9, 2018 at 10:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .