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?

  • $\begingroup$ Perhaps you should keep reading the textbook. $\endgroup$ – Yuval Filmus Mar 26 '18 at 12:47
  • $\begingroup$ 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? $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – user8469759 Mar 26 '18 at 13:56
  • $\begingroup$ It's basically the same thing. $\endgroup$ – Yuval Filmus Mar 26 '18 at 14:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.