Generating function of recursive algorithm with random subcalls

Question

I was presented with the following algorithm. As input the algorithm gets an array of length $n \geq 0$. If $n \geq 2$ then for each $k \in \{1, 2, ..., n\}$ the algorithm calls itself recursively with the probability $\frac{1}{2}$ with the array of length $k$. Using generating functions I have to get to the formula which estimates the average number of calls depending on $n$. I have checked analysis of QuickSort algorithm that was performed in similar terms. My proposition for recursive equation, regarding my problem, is as follows: $q_n = 1 + \frac{1}{2}\sum_{k=1}^nq_k$.

Is proposed recursive equation correct (will it estimate the number of calls correctly)? If so, then how, using generating functions, can I get the closed-form expression for the $q_n$?

Answer 1

The recurrence $q_n=1+\frac12\sum_{k=1}^nq_k$ for $n\ge 2$ appears to be correct, and you have the initial conditions $q_0=0$ and $q_1=1$. I would modify the recurrence slightly to make it correct for all $n\ge 0$ on the assumption that $q_n=0$ for all $n<0$:

$$q_n=1+\frac12\sum_{k=1}^nq_k-[n=0]-\frac12[n-1]\;,\tag{1}$$

where the square brackets are Iverson brackets, and we can include $k=0$ because $q_k=0$. Now multiply $(1)$ by $x^n$ and sum over $n\ge 0$:

$$\sum_{n\ge 0}q_nx^n=\sum_{n\ge 0}x^n+\frac12\sum_{n\ge 0}\left(\sum_{k=0}^nq_i\right)x^n-1-\frac{x}2\;.\tag{2}$$

The lefthand side of $(2)$ is the desired generating function, say $g(x)$, so we have

$$\begin{align*} g(x)&=\frac1{1-x}-1-\frac{x}2+\frac12\sum_{n\ge 0}\left(\sum_{k=0}^nq_i\right)x^n\\ &=\frac12\left(\frac{x+x^2}{1-x}+\sum_{n\ge 0}\left(\sum_{k=0}^nq_i\right)x^n\right)\;. \end{align*}$$

Now recognize $\sum_{n\ge 0}\left(\sum_{k=0}^nq_i\right)x^n$ as the Cauchy product of $\sum_{n\ge 0}q_nx^n$ and a very simple power series whose corresponding function $f(x)$ you know, so that

$$2g(x)=\frac{x+x^2}{1-x}+f(x)g(x)\;.$$

You can then solve for $g(x)$:

$$g(x)=\frac{x+x^2}{(1-x)(2-f(x))}\;.$$

And if you’ve done this correctly, you’ll easily be able to expand $g(x)$ into a power series from which you can read off the coefficients $q_n$.