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.
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:
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.