3
$\begingroup$

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

$G(t,u)=E\left(1+\frac{1-u}{u}t,u\right),$

(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?

  • 0
    Corrected one more typo on last equation..2012-07-20

1 Answers 1

4

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*}$

  • 0
    @Anuj: You're welcome. Glad to help.2012-07-20