HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

Applying the Master Theorem on Merge sort

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
themergemastersorttheoremapplying

Problem

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

Solution

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

Context

StackExchange Computer Science Q#62427, answer score: 6

Revisions (0)

No revisions yet.