A Didactic Analysis of Functional Queues
A Didactic Analysis of Functional Queues

Summary/Abstract: When first introduced to the analysis of algorithms, students are taught how to assess the best and worst cases, whereas the mean and amortized costs are considered advanced topics, usually saved for graduates. When presenting the latter, aggregate analysis is explained first because it is the most intuitive kind of amortized analysis, often involving enumerative combinatorics. We show how the aggregate analysis of functional queues can be carried out accurately and graphically, without combinatorics nor analytical tools like asymptotics, hence making it amenable to undergraduates. Our presentation is independent of any programming language.

• Details
• Contents