Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to find out the average case analysis of median of 3 - quick select. The recurrence relation is
\begin{equation} C_{n,j} = 1 + \sum_{k=1}^{j-1}\pi_{n,k}C_{n-k,j-k} + \sum_{k=j+1}^{n} \pi_{n,k}C_{k-1,j} \end{equation} where $$\pi_{n,k} = \frac{(n-k)(k-1)}{{{n}\choose{3}}}.$$

First we consider $$C_j(x) = \sum_{n} C_{n,j}x^n.$$ Multiplying by ${{n}\choose{3}}\; x^{n-3}$ and summing over $n$ on both sides $$\sum_{n\geq 3}{{n}\choose{3}} x^{n-3}\; C_{n,j} =\sum_{n\geq 3}{{n}\choose{3}}(1+\sum_{k=1}^{j-1}\pi_{n,k}C_{n-k,j-k} + \sum_{k=j+1}^{n} \pi_{n,k}C_{k-1,j} )\; x^{n-3} $$ We expand out the binary coefficients, since ${n\choose 3}=n(n-1)(n-2)/6$, so we get $$\begin{aligned}\frac{1}{6} &\; \sum_{n\geq 3}n(n-1)(n-2) \;x^{n-3}\; C_{n,j}\\ &=\sum_{n\geq 3} \frac{n(n-1)(n-2)}{6} x^{n-3} +\sum_{n\geq 3} \sum_{k=1}^{j-1}(k-1)(n-k)C_{n-k,j-k}x^{n-3} \\ &\qquad+\sum_{n\geq 3} \sum_{k=j+1}^{n} (k-1)(n-k)C_{k-1,j}\; x^{n-3}\end{aligned} $$ But look, the left hand side is precisely $$\frac{1}{6} \sum_{n\geq 3}n(n-1)(n-2) \;x^{n-3}\; C_{n,j}=\frac{C^{'''}_{j}(x)}{6}$$ so we have $$ \begin{aligned} 1/6 C_j^{'''}(x) &= \sum_{n\geq 3} n(n-1)(n-2)/6\; x^{n-3} +\sum_{n\geq 3} \sum_{k=1}^{j-1}(k-1)(n-k)C_{n-k,j-k}x^{n-3} \\ &\qquad+\sum_{n\geq 3} \sum_{k=j+1}^{n} (k-1)(n-k)C_{k-1,j}\; x^{n-3} \\ &= 1/6\; \sum_{n\geq 3} n(n-1)(n-2)\; x^{n-3} \rightarrow (1)\\ &\qquad +\sum_{n\geq 3} \sum_{k=1}^{j-1}(k-1)(n-k)C_{n-k,j-k}x^{n-3} \rightarrow (2)\\ &\qquad +\sum_{n\geq 3} \sum_{k=j+1}^{n} (k-1)(n-k)C_{k-1,j}\; x^{n-3} \rightarrow (3) \end{aligned}$$

Lets solve each parts named $(1), (2)$ and $(3)$ separately. $$\tag{1} \sum_{n\geq 3} n(n-1)(n-2)\; x^{n-3} = \frac{d^4}{dx^4}\sum_{n\geq 0} x^{n} = \frac{d^4}{dx^4} (\frac{1}{(1-x)}) = \frac{6}{(1-x)^4} $$

The second term (2) $$\tag{2} \sum_{n\geq 3} \sum_{k=1}^{j-1}(k-1)(n-k)C_{n-k,j-k}x^{n-3} = $$ Since, $C_j(x) = \sum C_{n,j}x^n$ we have $C_{j-k}(x) = \sum C_{n,j-k}x^n$ or $C_{j-k}(x) = \sum C_{n-k,j-k}x^{n-k}$
This term,$ \sum_{n\geq 3}(n-k)C_{n-k,j-k}x^{n-3} $ can be rewritten as $\sum_{n\geq 3}(n-k)C_{n-k,j-k}x^{n-k}\;x^{k-3} = x\; C_{j-k}^{'}\;x^{k-3} =C_{j-k}^{'}\;x^{k-2}$
$\sum_{n\geq 3} \sum_{k=1}^{j-1}(k-1)(n-k)C_{n-k,j-k}x^{n-3} = \sum_{k=1}^{j-1} (k-1)x^{k-2}C_{j-k}^{'}\;$

The third term (3) is $$\begin{aligned} \sum_{n\geq 3} &\sum_{k=j+1}^{n}& (k-1)(n-k)C_{k-1,j}\; x^{n-3} \\ &= \sum_{n\geq 3} \sum_{k=1}^{n} (k-1)(n-k)C_{k-1,j}\; x^{n-3} \;\rightarrow (3.1)\\ &\qquad - \sum_{n\geq 3} \sum_{k=1}^{j} (k-1)(n-k)C_{k-1,j}\; x^{n-3}\; \rightarrow (3.2)\end{aligned}$$ We have $$\tag{3.1} \sum_{n\geq 3} \sum_{k=1}^{n} (k-1)(n-k)C_{k-1,j}\; x^{n-3} = \sum_{n\geq 2} \sum_{k=1}^{n} (k-1)(n+1-k)C_{k-1,j}\; x^{n-2}$$ Here, $a = k-1, b = n+1 -k ;\;a+b = n $
$=1/x^2\;\sum_{n\geq 0} \sum_{a+b=n} (a)(b)C_{b,j}\; x^{n} = 1/x^2 \;[\sum_{a\geq 0} a\;x^a] \;[\sum_{b\geq 0} bC_{b,j}\;x^b ]$
$= 1/x^2 \; x \frac{d}{dx} \frac{1}{(1-x)} \; x \; \frac{d}{dx}\sum_{b=1}^{\infty} C_{b,j} \;x^b $
Since, $C_{b,j} x^b = C_j$
hence, $ = \frac{C^{'}}{(1-x)^2} $

{3.2}: How can we solve this? $\sum_{n\geq 3} \sum_{k=1}^{j} (k-1)(n-k)C_{k-1,j}\; x^{n-3} = $

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.