Trying to modify a merge sort by recursively splitting an array of size n into k sorted subarrays k > 2 and merging these subarrays. Time for merging is c(k-1)n. Specify the recurrence relation and derive the closed-form formula for sorting time Tk(n) of the modified merge sort for an arbitrary k. Then determine whether the modified merge sort could be faster for some k > 2 than the conventional one (k =2) with the sorting time T2(n) = cn log2n.
So I started by doing the following:
Each time when we split an array into 2 we get T(n/2) in the equation. So first time n/2, then for next we divide 2 again which is (n/2)/2.
Therefore from this we can get 2T(n/2) + cn.
What I don’t understand is what to do next I also did some working to get T2(n) = cnlog2n which I don’t think is useful for the moment, am just confused on what the next step is.
Best Answer
You can in the iterative manner, just substitute the recurrence expression back
So you have a basic $$T(n) = 2T\left(\frac{n}{2}\right) + cn$$
Therefore, for any $k$ $$T\left(\frac{n}{2^k}\right) = 2T\left(\frac{n}{2^{k+1}}\right) + c\cdot\frac{n}{2^k}$$
So, $$T(n) = 2T\left(\frac{n}{2}\right) + cn =$$ $$ = 2\left(2T\left(\frac{n}{4}\right) + c\cdot\frac{n}{2}\right) + c\cdot n = $$ $$ 4T\left(\frac{n}{4}\right) + 2c\cdot n = \ldots = 2^kT\left(\frac{n}{2^k}\right) + kcn$$
Here, you should think "how deep you can go in the recursion?". Recall, in mergesort, the array of size $1$ is sorted and we stop diving.
I.e. $T\left(\frac{n}{2^{k_{\text{max}}}}\right) = T(1)$, then $k_{\text{max}} = \log n$.
This concludes in $$T(n) = 2^{k_{\text{max}}}T(1) + k_{\text{max}}cn = nT(1) + cn\log n$$
$T(1)$ is some constant.
Regarding this $k$-split. No matter, how optimal you are making it, we know you can't theoretically drop under $\Theta(n \log n)$, why bother than?