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