# Advantage of using generating functions in analyzing an algorithm

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?

• Perhaps you should keep reading the textbook. – Yuval Filmus Mar 26 '18 at 12:47
• Of course I'll keep reading... But just for sake of not missing the point of all this, is it hard to provide an example? – user8469759 Mar 26 '18 at 12:56

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.
• Is there a relationship between generating function and the $Z$- transform used in DSP? from the definition they look the same, and as far as I've seen this is used mostly for linear difference equations with constant coefficients. I remember the avarage case analysis for the quicksort in CLRS that was quite difficult. – user8469759 Mar 26 '18 at 13:56