Introduction to Asymptotic Notation

Dr. Russ Miller

January 3, 1997

We use Θ to mean ‘order exactly’, O to mean ‘order at most’, and Ω to mean ‘order at least’. Definition of Θ: Given nonnegative functions f and g defined on the positive integers, we write f = Θ(g) if and only if there are positive constants C_{1}, C_{2}, and a positive integer N such that

C_{1} ∗ g(n) ≤ f(n) ≤ C_{2} ∗ g(n), whenever n > N.

Definition of O: Given nonnegative functions f and g defined on the positive integers, we write f =O(g) if and only if there is a positive constant C and an integer N such that

f(n) ≤ C ∗ g(n), for all n > N.

Definition of Ω: Given nonnegative functions f and g defined on the positive integers, we write f = Ω(g) if and only if there is a positive constant C and an integer N such that

C ∗ g(n) ≤ f(n), for all n > N.

When using order notation, one wants to use the simplest function possible within the Θ, O, or Ω. The idea is to use the notation to reduce complicated functions to simpler ones whose behavior is easier to understand.

Proposition 1: Suppose f and g are positive functions defined on the positive integers, and that lim_{n→∞} \frac{f(n)}{g(n)} = a, for some nonzero a. Then f = Θ(g).

Proof: lim_{n→∞} \frac{f(n)}{g(n)} = a means that for any c > 0 there is an integer N such that |\frac{f(n)}{g(n)} − a| ≤ c, for all n ≥ N. If we chose c = \frac{a}{2} then there is an N such that \frac{a}{2} ≤ \frac{f(n)}{g(n)} ≤ \frac{3a}{2} for all n ≥ N. So, (\frac{a}{2}) ∗ g(n) ≤ f(n) ≤ (\frac{3a}{2}) ∗ g(n), for all n ≥ N. □

Proposition 1 is useful because there are many techniques, such as L’Hopital’s rule, for evaluating limits. However, there are some instances where Proposition 1 cannot be used.

For example, 2 + sin(n) = Θ(1), even though lim_{n→∞} \frac{[2+sin(n)]}{1} is undefined. Examples of Θ: If f(n) = 3n + 6 and g(n) = n, then f(n) = Θ(g(n)), or f = Θ(g), or

3n + 6 = Θ(n), as can be seen by using C_{1} = 3, C_{2} = 4, and N = 5.

Notice that if f = Θ(g) then g = Θ(f), since if there are positive constants C_{1}, C_{2}, and N such that C_{1}∗g(n) ≤ f(n) ≤ C_{2}∗g(n) for all n > N, then (\frac{1}{C_{2}} )∗f(n) ≤ g(n) ≤ (\frac{1}{C_{1}} )∗f(n), for all n > N.

3n+2 = Θ(n). 10n^{2} +4n+2 = Θ(n^{2}). 10n^{2} +4n+2 ≠ Θ(n). 10∗log n+4 = Θ(log n).□

Useful Properties of Θ:

1. If f(n) = Θ(h(n)) and g(n) = Θ(h(n)), then (f + g)(n) = Θ(h(n)).

2. If f(n) = Θ(g(n)) and g(n) = Θ(h(n)), then f(n) = Θ(h(n)).

3. a_{k}n^{k} + a_{k−1}n^{k−1} + ⋯ + a_{1}n + a_{0} = Θ(n^{k}), a_{k} > 0.

4. log_{a}(n) = Θ(log_{b}(n)) for any a, b > 1.

5. ∑_{i=1}^{n} i = Θ(n^{2})

6. ∑_{i=1}^{n} log_{a}(i) = Θ(n log n), a > 1.

7. ∑_{i=1}^{n} \frac{1}{i} = Θ(log(n)).

8. ∑_{i=1}^{n} \frac{1}{i^{2}} = Θ(1).

9. If f(n) = Θ(h(n)), g(n) = Θ(h(n)), and f(n) ≤ e(n) ≤ g(n), then e(n) = Θ(h(n)).

O and Ω Notation

It is not always possible to determine the behavior of an algorithm using Θ-notation. For example, given a problem with n inputs, we may have an algorithm to solve the problem which takes Dn^{2} time when n is even and Cn time when n is odd. Or, we may only be able to prove that an algorithm never uses more than En^{2} time and never less than F n time. In either circumstance we can claim neither Θ(n) nor Θ(n^{2}) to be the order of the time usage of the algorithm. O and Ω notation will allow us to give at least partial information.

Proposition 2: Suppose f and g are positive functions defined on the positive integers, and that lim_{n→∞} \frac{f(n)}{g(n)} = 0, then f =O(g). □

Examples of O: 3n + 2 =O(n), since 3n + 2 ≤ 4n, for all n ≥ 2. 100n + 6 =O(n), since 100n + 6 ≤ 101n, for all n ≥ 10. 10n^{2} + 4n + 2 =O(n^{2}), since 10n^{2} + 4n + 2 ≤ 11n^{2}, for all n ≥ 5. 3n + 2 ≠O(1), since 3n + 2 is not less than or equal to c for any constant c and all n, n ≥ N. 10n^{2} + 4n + 2 ≠O(n). 10n^{2} + 4n + 2 =O(n^{4}). □

Proposition 3: Suppose f and g are positive functions defined on the positive integers, and that lim_{n→∞} \frac{f(n)}{g(n)} = ∞, then f = Ω(g). □

Examples of Ω: 3n + 2 = Ω(n), since 3n + 2 ≥ 3n for all n ≥ 1. 100n + 6 = Ω(n), since 100n + 6 ≥ 100n for all n ≥ 1. 10n^{2} + 4n + 2 = Ω(n^{2}) since 10n^{2} + 4n + 2 ≥ n^{2} for all n ≥ 1. 10n^{2} + 4n + 2 = Ω(n). 10n^{2} + 4n + 2 = Ω(1). □

Useful Properties of O and Ω:

1. f = Θ(g) if and only if f =O(g) and f = Ω(g).

2. If f =O(h) and g =O(h) then f + g =O(h).

3. If f = Ω(h) and g = Ω(h) then f + g = Ω(h).

4. If f =O(g) and g =O(h) then f =O(h).

5. If f = Ω(g) and g = Ω(h) then f = Ω(h).

6. Suppose 0 < a < b. Then n^{a} =O(n^{b}) and n^{b} = Ω(n^{a}).

7. Suppose 0 < a and 1 < b, then log_{b} n =O(n^{a}) and n^{a} = Ω(log_{b} n).

8. Suppose 1 < c and 0 < a, then n^{a} =O(c^{n}) and c^{n} = Ω(n^{a}).