Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was wondering to myself what the actual run time of Mergesort was, so I thought like this:

We have the sort operation that takes time $s(2) = 1$ and $s(1) = 0$. Merging two sorted sequences with length $k$ and $l$ takes $m(k, l) = k+l$ time. If we want to sort a sequence with $n$ elements we can also sort the sequences with index $\left[0, n/2\right>$ and $\left[n/2, n\right>$ with added cost $m(n/2,n/2) = n$.

We already know $s(2) = 1$. Now we also know that $s(n) = 2 \cdot s(n/2) + n$. In other words: $2(n + 2(n/2 + \dots 2(2 + s(2))) = s(n)$. If I reverse that I see that $s(2n) = 2(n + s(n))$.

I note that if we have a sequence with $2^k$ elements we can divide this sequence and subsequences in two $\log_2(2^k) - 1 = k-1$ times to get sequences of length 2.

Now that's where I'm stuck. I have no idea how to expand $s(2n) = 2(n + s(n))$. Can someone give me a push in the right direction?

Please be gentle, I'm only known with high-school math.

share|improve this question

1 Answer 1

Since mergesort has $n\log n$ complexity (which you can learn from Wikipedia in case you don't already know it), a reasonable guess for $s(n)$ would be $s(n)=\alpha n\log n$. Also, note that adding a multiple of $n$ to a solution yields another solution, so we can use the ansatz $s(n)=\alpha n\log n+\beta n$. Substituting this into your recurrence yields

$$\alpha2n\log(2n)+\beta2n=2(n+\alpha n\log n+\beta n)\;,$$

$$\alpha2n(\log2+\log n)=2n+2\alpha n\log n\;,$$

$$\alpha2n\log2=2n\;,$$

$$\alpha\log2=1\;,$$

$$\alpha=\frac1{\log2}\;,$$

so $s(n)=n\log n/\log 2+\beta n=n\log_2n+\beta n$.

Then substituting the initial value $s(2)=1$ yields $s(2)=2\log_22+2\beta=2+2\beta=1$ and $\beta=-\frac12$ and finally $s(n)=n\log_2n-\frac12n$. Note that your other initial value is inconsistent with the recurrence; I'm not sure how you arrived at these initial values, but if that's what you want, you'll have to treat $s(1)=0$ as a special case.

share|improve this answer
    
I don't think that assuming mergesort has $n \log n$ complexity because Wikipedia says so is correct for a mathematical argument. Also, $s(1) = 0$ because a sequence of 1 is already sorted and $s(2) = 1$ because 2 elements can be sorted using one comparison (or one time). –  orlp Nov 8 '11 at 22:18
    
@nightcracker: That's a misunderstanding. I didn't assume it, I just used it as an ansatz to find the solution. Once the solution is found, you can check it rigorously without recourse to Wikipedia. Concerning the initial values: You can do it that way, but then you're not solving the $n=2$ case by recursion, so there's no reason to expect the recurrence to hold for that case, so then $s(1)=0$ is a special case disjoint from the others. –  joriki Nov 8 '11 at 22:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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