2
$\begingroup$

The problem was from an exam, I spent much time wrapping my head up around this kind of problems, so I decided to ask for help ;(

Problem:

We implement a merge sort algorithm to sort $n$ items. The algorithm will divide the set into 2 roughly equal-size halves, and merge the 2 halves after each half set is recursively sorted. Because the item comparison is complicated, the merge process takes $\theta(m\sqrt{m})$ steps for input size $m$. What is the time complexity for this algorithm?

(a) $\theta{(n\log{n})}$
(b) $\theta{(n)}$
(c) $\theta{(n^2)}$
(d) $\theta{(n\sqrt{n})}$
(e) $\theta{(n\sqrt{n}\log{n})}$

What I tried:

  1. I know the merge sort normally can be written $S(n) = 2S(\frac{n}{2}) + n, S(1) = 1$, where the recursive function $S$ is the step cost of the merge sort for the size $n$.

  2. But the problem specifies the step costs to merge is $\theta(n\sqrt{n})$, I have to rewrite it as $S(n) = 2S(\frac{n}{2}) + \theta(n\sqrt{n}) = 2S(\frac{n}{2}) + n\sqrt{n}$. I have no idea how to transform it into the general solution...

Please help me, I will learn a lot from this problem! Thanks :)

$\endgroup$
  • $\begingroup$ Is the answer D? $\endgroup$ – Gokul Dec 10 '18 at 1:09
  • $\begingroup$ Sorry, I don't know the answer, welcome to share any idea! $\endgroup$ – OOD Waterball Dec 10 '18 at 3:48
3
$\begingroup$

You are on the right track.

Now that we have the recurrence relation $$S(n) = 2S(\frac{n}{2}) + \Theta(n\sqrt{n}),$$ Applying the case three of the master theorem, where $a=2$, $b=2$, $\epsilon=\frac12$, we will have $S(n)= \Theta( n\sqrt n)$.

I was stretching a bit when we were applying the master theorem since the regularity condition, the existence of such $c>0$ required for case three is not necessarily satisfied. What I really meant is that we can find two constant $0<c_1<c_2$ such that $c_1n\sqrt n\le S(n)-2S(\frac n2) \le c_2n\sqrt n$ for all $n$. Define $S_1$ by $S_1(n) = 2S_1(\frac{n}{2}) + c_1n\sqrt{n}$ and $S_2$ by $S_2(n) = 2S_2(\frac{n}{2}) + c_2 n\sqrt{n}$ with the same initial condition as $S$. Now we can apply case three of the master theorem to $S_1$ and $S_2$ to get the same $\Theta$ bound, since the regularity condition is satisfied with $1>c=0.8>\sqrt2/2$. Since $S_1(n)\le S(n)\le S_2(n)$, S(n) has the same $\Theta$ bound.

In case you have not learned/are not allowed to use the master theorem, you may have to more or less prove case three of the master theorem by yourself. You could find a proof, for example, in CLRS.

$\endgroup$
  • $\begingroup$ Welcome! $\quad$ $\endgroup$ – Apass.Jack Dec 10 '18 at 12:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.