Comparison of Functions

1 Relationships

Like real numbers, many relational properties can be applied to asymptotic comparisons. One of the properties of real numbers that does not apply to asymptotic comparisons is trichotomy. For any two real numbers,

a

and

b

, exactly one of the following must hold:

a < b

a = b

, or

a > b

. Some functions however can not be asymptotically compared.

1.1 Transitivity

\begin{matrix} f (n) & = & Θ (g (n)) & and & g (n) & = & Θ (h (n)) & imply & f (n) & = & Θ (h (n)) \\ f (n) & = & O (g (n)) & and & g (n) & = & O (h (n)) & imply & f (n) & = & O (h (n)) \\ f (n) & = & Ω (g (n)) & and & g (n) & = & Ω (h (n)) & imply & f (n) & = & Ω (h (n)) \\ f (n) & = & o (g (n)) & and & g (n) & = & o (h (n)) & imply & f (n) & = & o (h (n)) \\ f (n) & = & ω (g (n)) & and & g (n) & = & ω (h (n)) & imply & f (n) & = & ω (h (n)) \end{matrix}

1.2 Reflexivity

\begin{matrix} f (n) & = & Θ (f (n)) \\ f (n) & = & O (f (n)) \\ f (n) & = & Ω (f (n)) \end{matrix}

1.3 Symmetry

\begin{matrix} f (n) & = & Θ (g (n)) & if and only if & g (n) & = & Θ (f (n)) \end{matrix}

1.4 Transpose Symmetry

\begin{matrix} f (n) & = & O (g (n)) & if and only if & g (n) & = & Ω (f (n)) \\ f (n) & = & o (g (n)) & if and only if & g (n) & = & ω (f (n)) \end{matrix}

2 Standard Notation and Common Functions

The following terms and rules should be familiar, as most will be a review of some standard mathematical notations.

2.1 Monotonicity

A function,

f (n)

is monotonically increasing if

m \leq n

implies

f (m) \leq f (n)

. Similarly, a function is monotonically decreasing if

m \geq n

implies

f (m) \geq f (n)

A function is strictly increasing if

m < n

implies

f (m) < f (n)

. Likewise, a function is strictly decreasing if

m > n

implies

f (m) > f (n)

2.2 Floors and Ceilings

The floor of

x

is the greatest integer less than or equal to

x

, and is denoted by

⌊ x ⌋

. The ceiling of

x

is the least integer greater than or equal to

x

, and is denoted by

lceil x ⌉

For all real $x$ : $x - 1 < ⌊ x ⌋ \leq x \leq ⌈ x ⌉ < x + 1$ .

2.3 Polynomials

Given a positive integer

d

, a polynomial in 4n4 of degree

d

is a function of the form:

p (n) = \sum_{i = 1}^{n} a_{i} n^{i}

where

a_{1}, a_{2}, \dots, a_{n}

are the coefficients of the polynomial. For example,

3 n^{5} - 2 n^{4} + 7 n^{2} + n - 8

is a polynomial of degree 5 with coefficients 3, -2, 0, 7, 1, and -8.

2.4 Exponentials

An important property of exponentials is that, for all real constants,

a

and

b

such that

a > 1

lim_{n \to \infty} \frac{n^{b}}{a^{n}} = 0

From this we can conclude that

n^{b} = o (a^{n})

Thus, any exponential function with a base strictly greater than 1 will grow faster than any polynomial function.

2.5 Logarithms

We will use the following notations throughout this course:

\begin{matrix} \lg n & = & \log_{2} n & (binary logarithm) \\ \ln n & = & \log_{e} n & (natural logarithm) \\ \lg^{k} n & = & (\lg n)^{k} & (exponentiation) \\ \lg \lg n & = & \lg (\lg n) & (composition) \end{matrix}

Like exponentials, we can relate polylogarithms to polynomials:

lim_{n \to \infty} \frac{\lg^{b} n}{n^{a}} = 0

We can then conclude that

\lg^{b} n = o (n^{a})

for any constant

a > 0

. So any polynomial function grows faster than any polylogarithmic function.

File translated from T_EX by T_TM, version 3.67.
On 31 Mar 2006, 18:12.