# Compute the general time complexity of a merge sort algorithm with specified complexity of the merge process

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

• Is the answer D? Dec 10 '18 at 1:09
• Sorry, I don't know the answer, welcome to share any idea! Dec 10 '18 at 3:48

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 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.
• Welcome! $\quad$ Dec 10 '18 at 12:24