Hashing in Computer Science: Fifty Years of Slicing and Dicing

CHAPTER 3

Asymptotic Analysis

3.1 GROWTH NOTATION FOR SEQUENCES

The first of the symbols for growth notation O, o, Ω, ω, ∼ were introduced in 1894 by number theorist Paul Bachmann [Bachman 1994]. It was popularized in the work of another German number theorist Edmund Landau (1877–1938)) and the symbol O is often referred to as the Landau symbol.

The notation a_n = O(b_n), read “a_n is big-Oh of b_n,” specifies that b_n ultimately provides a uniform upper bound on a_n; that is, C > 0 and a positive integer N exist such that

(3.1)

Examples of Sequence Growth

The notation a_n = Ω(b_n), read “a_n is big-Omega of b_n, specifies that b_n ultimately provides a corresponding uniform lower bound on a_n; that is, a C > 0 and a positive integer N exist such that

(3.2)

Examples 3.1

a) as n → ∞.

b) a_n = e^−An = O(n^−j) for every j > 0 as n → ∞.

c) as n → ∞.

d) as n → ∞.

e) as n → ∞.

We write a_n = ...