0

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.

Community
  • 1
Arnau
  • 341
  • 1
    The question is only asking about the merge step, why are you calculating the cost of the entire algorithm? – Michael Burr Jun 08 '18 at 23:37
  • 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. – Arnau Jun 09 '18 at 07:21

1 Answers1

1

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.

Badr B
  • 631
  • 5
  • 13
  • But I still don't understand. Why are my calculations not matching with this? I got that the merge part grows logarithmically, not linearly. – Arnau Jun 09 '18 at 07:15
  • @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. – Badr B Jun 09 '18 at 08:17
  • I'm not sure I understand... Could you break it down a little bit? I'm sorry. – Arnau Jun 09 '18 at 09:19
  • @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. – Badr B Jun 09 '18 at 09:53
  • Okay, then why is the answer (b) if it grows logarithmically? – Arnau Jun 09 '18 at 10:29
  • @Arnau The merge operation grows linearly. The number of "levels" grows logarithmicly. – Badr B Jun 09 '18 at 10:48
  • By merging operations you mean merging two elements? Like, in your example it would be 7, wouldn't it? – Arnau Jun 09 '18 at 11:09
  • @Arnau Merging two elements is $O(1)$. Merging two arrays of size $p$ and $q$ is $O(p+q)$. In this example, merging an entire level unto the next level is $O(n)$. – Badr B Jun 09 '18 at 11:15
  • But if merging two elements is $O(1)$, we can think of them as two arrays of size 1. Then, merging two arrays of size $p$ and $q$ would be $O(\frac{p}{2}+\frac{q}{2})$, right? – Arnau Jun 09 '18 at 11:55
  • @Arnau $O(1)$ meaning constant time. It'll be the same for any fixed value of $n$. And no it'll be $O(p+q)$, because $p+q$ is the total number of elements being merged. Nevertheless though, it'll still be linear time. – Badr B Jun 09 '18 at 12:01
  • Okay, so it asks for the solution with respect to time; not with respect to the number of elements. – Arnau Jun 09 '18 at 12:42
  • @Arnau Are you sure? When evaluating sorting algorithms, you always find it in terms of number of elements. This page explains things clearly: https://www.geeksforgeeks.org/merge-sort/ – Badr B Jun 09 '18 at 16:02
  • Well, if it asks the solution with respect to $n$, then I don't understand the answer. – Arnau Jun 09 '18 at 17:34
  • @Arnau Why not? – Badr B Jun 10 '18 at 01:32