Generating functions in analyzing algorithms

Question

I am reading a book on Algorithms and it was mentioned that generating functions are helpful in analyzing algorithms. I am not able to understand how it is useful? I request help here like giving an simple example how generating functions can be used in analyzing algorithms?

and also any good link on tutorial regarding generating functions with respect to computer algorithms.

Thanks!

BlackJack · Answer 1 · 2011-08-09 13:21:28Z

up vote 2 down vote

See Mathematical Methods in the Analysis of Algorithms and Data Structures by Flajolet for relevant information.

edited Aug 9 '11 at 13:21

BlackJack
2,91331947

answered Aug 9 '11 at 13:10

bpgergo
1211

5

Posting a single link as an answer is not recommended on StackExchange. It is better to quote a short summary of the referred article, to provide a valid (if brief) answer to the question in place, and to ensure that your answer stays (at least partially) valid even if the link breaks in the future. – Péter Török Aug 9 '11 at 13:21

@Péter: yup, you're right, I should have just post this link as a comment. – bpgergo Aug 9 '11 at 13:25

@BlackJack, thanks for editing – bpgergo Aug 9 '11 at 13:26

tskuzzy · Answer 2 · 2011-08-09 13:09:49Z

They can be used to find closed-form formulas for recurrence relations. They can also be used to analyze the asymptotic behavior of certain sequences. This is very useful tool when trying to find the time-complexity of recursive algorithms.

asked	1 year ago
viewed	121 times
active	1 year ago

Generating functions in analyzing algorithms

migrated from stackoverflow.com Aug 9 '11 at 13:08

2 Answers