Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am currently studying analysis of Algorithms and have come across a paper about Median of 3 partition for quick select. The authors have solved the recurrence using the generating functions and came up to a partial differential equation (eq 6 in the paper):

$$\frac{1}{6} \frac{\partial^2Q}{\partial z^2} - \left [ \frac{1}{(1-z)^2} + \frac{u^2}{(1-uz)^2} \right]Q = \frac{u}{(1-u)} \left [ \frac{1}{(1-z)^4} - \frac{u^3}{(1-uz)^4} \right].$$

Expressing $Q(z,u)$ as (eq 7 in paper)

$$Q(z,u) = \frac{1}{(1-z)^2(1-uz)^2}E(z,u)$$

and substitute $z = 1+t(1-u)/u$.


(eq 8 in paper) the original equation will transforms to:

$$t(1-t)\frac{\partial^2 G}{\partial t^2} + (-4+8t)\frac{\partial G}{\partial t} - 8G = 6(1-u)\frac{u(1-t)^4 - t^4}{t(1-t)}$$

(eq 9 in paper). Now, I am not able to understand how the authors get this equation because when I tried to solve using the same substitutions I get the below one:

$$t^2\frac{\partial^2 G}{\partial t^2} - 8t\frac{\partial G}{\partial t} + 2G \left [ 10 + \frac{u^2}{(1-u)^2} \right] = 6u^2t^2.$$

Are the both equations same or am I doing some mistake?

share|cite|improve this question
It seems you already know this and corrected it in your reproduction, but for others who look at the paper it might be helpful to know that there's a typo in equation (8) and $\mathcal Q$ on the left-hand side should be $\mathcal G$. (I also corrected a typo in your version of equation (8).) – joriki Jul 20 '12 at 5:54
@joriki: That typo is not easy to spot. Good eyes! – user26872 Jul 20 '12 at 7:47
Corrected one more typo on last equation.. – Anuj Jul 20 '12 at 8:35
up vote 4 down vote accepted

It looks like you are missing some terms. I give a few partial results that should allow you to track them down. $$\begin{eqnarray*} \frac{d}{dz} &=& \frac{dt}{dz} \frac{d}{dt} \\ &=& \frac{1}{dz/dt} \frac{d}{dt} \\ &=& \frac{u}{1-u} \frac{d}{dt} \\ \frac{d}{dz} Q(z) &\rightarrow& \frac{u}{1-u} \frac{d}{dt} \left(\frac{u^2}{(1-u)^4} \frac{1}{t^2(1-t)^2} G(t) \right) \\ &=& \frac{u^3}{(1-u)^5} \frac{1}{t^3(1-t)^3} [(t(1-t)G'(t) - 2(1-2t)G(t)] \hspace{5ex} \clubsuit \\ \frac{d^2}{dz^2} Q(z) &\rightarrow& \frac{u}{1-u} \frac{d}{dt} \left(\clubsuit\right) \end{eqnarray*}$$

share|cite|improve this answer
Got it. I was confused why I am not getting that $(1-t)$ term and now realized i did this mistake. Thanks for pointing it out. – Anuj Jul 20 '12 at 9:16
@Anuj: You're welcome. Glad to help. – user26872 Jul 20 '12 at 15:16

Your Answer


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.