Errata

Sorting: A Distribution Theory

Hosam M. Mahmoud

The author of  this book requested the following changes from the printers near the time of production. He was informed by the publisher that it is unfortunately  too late for this edition:

Page 28, Line 7 from the bottom:  The sentence The adversary then crosses out from the 6^4 possible patterns 3^4 patterns with the colors R, Y, or W  should be changed to The adversary then crosses out from the 6^4 possible patterns 6^4-3^4 patterns with the colors B, R, or W

Page 63: A large circle centered at the origin is intended in Figure 1.12

Page 121, Line 2 from the bottom and Page 369, Line 8: The symbol a.s. is supposed to appear above an equal sign (as for example the almost sure equality notation on Page 116, Line 3 )

Page 158, Line 2 from the bottom: Remove blank before period

Page 322, solution to Exercise 1.11.4: Each of the three equalities on Lines 4-6 is missing a O(1) term coming from an integral on the left side of the box. (The authors thanks Helmut Prodinger, University of the Witwatersrand, South Africa, for a useful discussion about this point)

Page 367, Line 5 from the bottom: , over A should be over A,

Page 370, Line 14: The phrase in theses cases a central limit theorems should read  in theses cases a central limit theorem

Page 391: Lindeberg, X. should become Lindeberg, J.

Page 393: The page number 371 should go one line down to index Slutsky, E. instead of Short circuit

The following two misprints have been reported by readers:

Page 104, Line 7 in the algorithm (Figure 3.1): i := h+1 should be i := s+1 (reported by David Butler, Oregon State University)

Page 105, Line 6: The punctuation between the two sentences During the first iteration of the outer loop. The first ... should be changed to a separating comma. The text should read During the first iteration of the outer loop.  The first ... (this error was reported by Robert Smythe, Oregon State University)

Lacuna:

Page 52, Line 9: Generally speaking, a sum of o_P(k^2) term, for k =1,...,n,  is not necessarily o_P(n^3), however it is true in this case and can be justified in the L_1 norm. The author is grateful for a related discussion with Tatsuie Tsukiji, Nagoya University, Japan and an anonymous referee of [1] below.

References

1.Tsukiji, T. and Mahmoud, H. (2001). A limit law for outputs in random circuits. Algorithmica, 31, 403-412.