3
$\begingroup$

Inspired by the excellent generatingfunctionology, I am trying to find the (ordinary) generating function for the recurrence describing worst-case runtime for merge sort:

$$ \begin{align*} T_0 &= 0 \\ T_{2n} &= 2\ T_n + n \\ T_{2n+1} &= 2\ T_n + n \end{align*} $$

Applying the transform to get a formal power series and simplifying, we get:

$$ \begin{align*} \sum_{n \ge 0} T_{2n}\ x^n &= \sum_{n \ge 0} \left(2\ T_n + n\right)\ x^n \\ &= 2 \sum_{n \ge 0} T_n\ x^n + \sum_{n \ge 0} n x^n \\ &= 2 \sum_{n \ge 0} T_n\ x^n + \left(\frac{d}{dx}\sum_{n \ge 0} x^{n+1}\right) - \sum_{n\geq 0} x^n \\ \frac{T(\sqrt{x}) + T(-\sqrt{x})}{2} &= 2\ T(x)\ + \frac{x}{(1-x)^2} \end{align*} $$

But I am not sure how to solve for $T(x)$ when square roots are involved. Is there a particular class of functions which model this relationship nicely? If I try to "invert" the recurrence, i.e.:

$$ \begin{align*} T_0 &= 0 \\ T_n &= 2 T_{\lfloor n/2 \rfloor} + n \end{align*} $$

I end up with a similar equation involving $T(x^2)$ instead. I know that $T_n = O(n \, \log n)$, but I'm having trouble using that information as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.