182 Index exponential function, 32, 37 factorization, 121 factors of the prime, 116 fair coin, 103, 107, 108 fast Fourier transform, 141 Fourier transform, 104 Gaussian distribution, 38 Gaussian paradigm, 110 Gaussian tail, 39, 69, 111 geometric distribution, 165 geometric series, 69, 120 Golden Ratio, 99 googol, 32, 170, 174 googolplex, 174 harmonic number, 51, 54, 60, 150, 165 Heilbronn triangle problem, 127 hierarchy of functions, 175 hyperbolic cosine, 108 hyperbolic functions, 109 implementation, 148 Inclusion-Exclusion Principle, 159, 160, 163 independent random variables, 104 indicator function, 94, 100 infinite ordinals, 176 infinitely often, 159 Information-Theoretic Lower Bound, 146 Insertion Sort, 147 integrable function, 48 inverse function, 34 iterated logarithm, 159, 170 Karatsuba’s algorithm, 141 labeled rooted forests, 83 labeled unicyclic graph, 88 Laplace transform, 103, 105, 106, 110 large deviations, 25, 103, 105–107 large numbers, 174 Law of the Iterated Logarithm, 151, 159 limit functions, 175 limit ordinal, 177 linearity of expectation, 100, 165 little oh, 29 little omega, 29 log star function, 170, 171 logarithm function, 2, 32 Lov´ asz local lemma, 95 mathematical game, 145 median, 147 Merge Sort, 144, 145, 148 monochromatic k-sets, 100 monochromatic graph, 93 monochromatic sets, 95 multiplying large matrices, 142 multiplying large numbers, 141 mutually independent, 107, 162 mutually independent events, 152 mutually independent random variables, 104 natural induction, 170 number of comparisons, 147 omega, 28 overhead function, 138 parametrization, 40, 61, 100, 166 parent function, 80 parent of a node, 72 perfect information game, 146 pivot, 148 Poisson distribution, 106, 159, 162, 164 Poisson paradigm, 162, 166, 168 pole, 45 Polya’s theorem, 25 polylog function, 2, 3, 29, 35 Pr¨ ufer sequence, 73, 79, 82, 83 Prime Number Theorem, 115, 123 Prisoners Game, 54 probabilistic method, 94 probability spaces, 152 Quicksort, 148 Ramsey number, 93, 94, 98 Ramsey’s theorem, 93 random coloring, 98 random graph, 167 random object, 93
Previous Page Next Page