When doing the "inexact" analysis of the Merge Sort, the literature that I have seen usually consider that the input is an array with a even quantity of numbers and the recurrence relation is:

$T(n) = 2T(n/2) + \Theta(n)$

But how I can formally prove that even if I consider any input, the complexity stays the same? While looking in the answers to the exercise 4.3-5 of the book Introduction to Algorithms on this site, he mention the recurrence for the odd sized input is as follow:

$T(n) = T((n-1)/2) + T((n+1)/2) + \Theta(n)$

And justifies that:

However, shifting the argument in $n.log(n)$ by a half will only change the value of the function by at most $\frac{1}{2}\frac{d}{dn}(n.log(n)) = \tfrac{log(n)}{2} + 1$, but this is $o(n)$ and so will be absorbed into the $\Theta(n)$ term.

But I did not understand his justification very well. Somebody could explain to me?

(Exercise 4.3-5: Show that $\Theta(n.log(n))$ is the solution to the "exact" recurrence for merge sort.)

  • 2
    $\begingroup$ What did you try and where did you get stuck? Please explain in detail what it is that confuses you. Otherwise, we cannot even begin to help you. Please edit your question to update with the new info. Thanks. $\endgroup$
    – Discrete lizard
    Mar 26 '18 at 7:58
  • 1
    $\begingroup$ Well, this is still a far shot of "exact", but well. Hint: Construct recurrences $T'$ and $T''$ s.t. $T'(n) \leq T(n) \leq T''(n)$ for (almost) all $n$. If $T' \in \Theta(T'')$, then by sandwiching $T \in \Theta(T')$ as well. $\endgroup$
    – Raphael
    Mar 26 '18 at 10:12
  • $\begingroup$ Another approach is to investigate the proof of the Master theorem and show that constant (!) offsets from $a/b$ do not change the result. $\endgroup$
    – Raphael
    Mar 26 '18 at 10:13

Let us consider the recurrence $$ T(n) = \begin{cases} 1 & \text{if } n = 1, \\ T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + n & \text{if } n \geq 2. \end{cases} $$ Using OEIS (A033156), we find that the exact solution to this recurrence is $$ T(n) = n(\lfloor \log_2 n \rfloor + 3) - 2^{\lfloor \log_2 n \rfloor + 1}. $$ Curiously, OEIS presents a different recurrence relation with the same solution: $$ T(n) = \begin{cases} 1 & \text{if } n = 1, \\ T(n-1) + \lfloor T(n-1)/(n-1) \rfloor + 2 & \text{if } n \geq 2. \end{cases} $$ The OEIS entry contains references to articles analyzing the recurrence in the context of divide-and-conquer, which you might find helpful if you want to analyze similar such recurrences.


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.