Advantage of using generating functions in analyzing an algorithm

Question

I'm reading through the first chapters of "Introduction to the analysis of algorithm" by Sedgewick. I wasn't familiar with the use of generating functions, and complex analysis in general to analyse algorithms. I do understand the use of the tool is in practice simple (at least it seems to me in that way from what I read so far).

I still don't get though what's the particular advantage of using a generating function over standard techniques of difference equations when analysing some recurrence extrapolated by some algorithm.

What's the benefit of using generating functions?

I can also see "analytic combinatoric" as topic, I haven't read through that yet, what's the advantage of that formalism instead? Is there some case where analysing in that way is really easy while using standard technique isn't?

Answer 1

Generating functions can be used to solve recurrence relations more complicated than linear recurrence relations with constant coefficients. As an example, let us consider quicksort (credit: lecture notes of Rezaul A. Chowdhury). Let us denote by $t_n$ the average number of comparisons performed by quicksort when the pivot is chosen at random. We have $t_0 = 0$ and for $n \geq 1$, $$ t_n = n-1 + \frac{1}{n} \sum_{k=1}^n (t_{k-1} + t_{n-k}) = n-1 + \frac{2}{n} \sum_{k=0}^{n-1} t_k. $$ Some work shows that the generating function $T(z)$ of the $t_n$ is $$ T(z) = \sum_{n=0}^\infty t_n z^n = \frac{2\log \frac{1}{1-z} - 2z}{(1-z)^2}. $$ From this it is not hard to extract the formula $$ t_n = 2(n+1)H_n - 4n. $$

In this particular case, there are more direct ways to calculate $t_n$. However, in more sophisticated situations, such tricks might not work. Furthermore, generating functions lead to mechanical manipulations - in fact, a software package can probably convert the recurrence for $t_n$ to the generating function, and hence to the exact expression. In this sense, generating functions generalize linear recurrence relations with constant coefficients by providing a large class of recurrences whose asymptotics can be ascertained.