I found the proof below in a textbook. I would like to know why it is important for the proof that it uses $\lceil \frac{n}{2} \rceil$ instead of just $\frac{n}{2}$? I know that you can't split into calls which aren't natural numbers, but how do I present this argument formally?

The proof:

The recursion splits the problem into two sub problems, each with at most $\lceil \frac{n}{2} \rceil$ elements. Therefore, we can apply the Master Theorem with $a = b = 2$. So, $\log_b{a}$ = 1. The cost of splitting is $0$ comparisons, and that of combining is at most $n−1$ comparisons. Hence the cost of split/combine is $\Theta(n) = \Theta(n\log_b{a})$, so we are in the second case of the Master Theorem, and therefore the total cost is $\Theta(n\log n)$.

  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Aug 9 '16 at 13:38

You can't use $n/2$ since this bound just isn't always true. Suppose that $n = 5$. It is not the case that you can split an array of length 5 into two arrays of length 2.5. It's not even true that you can split it into two arrays of length at most 2.5. But you are able to split it into two arrays of length at most $\lceil 2.5 \rceil = 3$.

Note that the textbook estimates the time it takes to sort an array with at most $n$ elements (rather than the time it takes to sort an array with exactly $n$ elements).

  • $\begingroup$ Right. This is a base case which is handled separately by the algorithm. The analysis mirrors the algorithm. $\endgroup$ – Yuval Filmus Aug 9 '16 at 14:23

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.