0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I think $c(k-1)n$ for merging is bad and this even calls for it never to be better than a standard implementation. From my short thinking, you can speed-up merging, by managing a sorted array of current pointers, so the whole merging time falls to $c n \log k$ (for insertion of next element, after minimal was picked). $\endgroup$
    – dEmigOd
    Commented Apr 14, 2018 at 5:16

1 Answer 1

2
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ Thank you! makes much more sense now $\endgroup$
    – M.Jones
    Commented Apr 14, 2018 at 5:53

You must log in to answer this question.

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