Volume 3, Issue 2 (November 2004)                   JIRSS 2004, 3(2): 251-270 | Back to browse issues page

XML Persian Abstract Print

Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Prodinger H. Periodic Oscillations in the Analysis of Algorithms and Their Cancellations. JIRSS. 2004; 3 (2) :251-270
URL: http://jirss.irstat.ir/article-1-112-en.html
Abstract:   (8978 Views)
A large number of results in analysis of algorithms contain fluctuations. A typical result might read “The expected number of . . . for large n behaves like log2 n + constant + delta(log2 n), where delta(x) is a periodic function of period one and mean zero.” Examples include various trie parameters, approximate counting, probabilistic counting, radix exchange sort, leader election, skip lists, adaptive sampling. Often, there are huge cancellations to be noted, especially if one wants to compute variances. In order to see this, one needs identities for the Fourier coefficients of the periodic functions involved. There are several methods to derive such identities, which belong to the realm of modular functions. The most flexible method seems to be the calculus of residues. In some situations, Mellin transforms help. Often, known identities can be employed. This survey shows the various techniques by elaborating on the most important examples from the literature.
Full-Text [PDF 209 kb]   (2583 Downloads)    

Received: 2011/08/26 | Accepted: 2015/09/12 | Published: 2004/11/15

© 2015 All Rights Reserved | Journal of The Iranian Statistical Society