Asymptotic Notation

Asymptotic notation consists of six symbols used to describe the relative growth rates of functions. These six symbols are defined in the table below.

NotationDescriptionDefinition
f=Θ(g)f = \Theta(g)ff grows at the same rate as ggThere exists a n0n_0 and constants c1,c2>0c_1, c_2 > 0 such that for all n>n0n > n_0, c1g(n)≤∥f(n)∥≤c2g(n)c_1g(n) \leq \|f(n)\| \leq c_2g(n).
f=O(g)f = O(g)ff grows no faster than ggThere exists a n0n_0 and a constant c>0c > 0 such that for all n>n0n > n_0, ∥f(n)∥≤cg(n)\|f(n)\| \leq cg(n).
f=Ω(g)f = \Omega(g)ff grows at least as fast as ggThere exists a n0n_0 and a constant c>0c > 0 such that for all n>n0n > n_0, cg(n)≤∥f(n)∥cg(n) \leq \|f(n)\|.
f=o(g)f = o(g)ff grows slower than ggFor all c>0c > 0, there exists a n0n_0 such that for all n>n0n > n_0, ∥f(n)∥≤cg(n)\|f(n)\| \leq cg(n).
f=ω(g)f = \omega(g)ff grows faster than ggFor all c>0c > 0, there exists a n0n_0 such that for all n>n0n > n_0, cg(n)≤∥f(n)∥cg(n) \leq \|f(n)\|.
f∼gf \sim gf/gf/g approaches 1lim⁡n→∞f(n)g(n)=1\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1

Testing for Same Growth Rate

f(n) and g(n) have the same growth rate if f(n) \text{ and } g(n) \text{ have the same growth rate if }

lim⁡N→∞f(N)g(N)=c,0<c<∞\lim_{N \to \infty} \frac{f(N)}{g(N)}=c, 0 < c < \infty

if c is some constant→f(N)=Θ(g(N))\text{if } c \text{ is some constant} \rightarrow f(N)=\Theta(g(N))

Note: No little theta exists

3 Rules

  1. Additive and Multiplicative Property

    If T1(n)=O(f(n))T_1(n) = O(f(n)) and T2(n)=O(g(n))T_2(n) = O(g(n)), then

    (a) T1(n)+T2(n)=O(f(n)+g(n))T_1(n) + T_2(n) = O(f(n) + g(n)) (intuitively and less formally it is O(max(f(n),g(n)))O(\text{max}(f(n), g(n)))),

    (b) T1(n)×T2(n)=O(f(n)×g(n))T_1(n) \times T_2(n) = O(f(n) \times g(n)).

  2. If T(n)T(n) is a polynomial of degree kk, then T(n)=Θ(nk)T(n) = \Theta(n^k)

  3. log⁡k(n)=O(n)\log^k(n) = O(n) for any constant kk

    a. This means that no matter what power of kk, it will not surpass O(n)O(n). b. However: log⁡k(n)\log^k(n) has a faster growth rate than log⁡(n)\log(n).

Quiz

Question 1

If f(n)=O(1)f(n) = O(1) and g(n)=O(n)g(n) = O(n), determine if the following statements are true or false.

  • f(n)=Θ(g(n))→False, constant function does not grow at the same rate as nf(n) = \Theta(g(n)) \rightarrow \text{False, constant function does not grow at the same rate as } n
  • f(n)=o(g(n))→True. f(n) grows at a slower rate than g(n)f(n) = o(g(n)) \rightarrow \text{True. } f(n) \text{ grows at a slower rate than } g(n)
  • f(n)=O(g(n))→True. f(n) is bounded above by some constant multiple of g(n)f(n) = O(g(n)) \rightarrow \text{True. } f(n) \text{ is bounded above by some constant multiple of } g(n)
  • f(n)=ω(g(n))→False. It would mean that f(n) grows faster than g(n)f(n) = \omega(g(n)) \rightarrow \text{False. It would mean that } f(n) \text{ grows faster than } g(n)

Question 2

Given f(n)=10n5+5n2+30nf(n) = 10n^5 + 5n^2 + 30n and g(n)=3n3g(n) = 3n^3, determine the validity of the following:

  • f(n)=O(n5)→Truef(n) = O(n^5) \rightarrow \text{True}
  • g(n)=O(n3)→Trueg(n) = O(n^3) \rightarrow \text{True}
  • f(n)=Θ(g(n))→False. n5 grows faster than n3f(n) = \Theta(g(n)) \rightarrow \text{False. } n^5 \text{ grows faster than } n^3
  • f(n)=Ω(g(n))→True. f(n) grows at least as fast as g(n)f(n) = \Omega(g(n)) \rightarrow \text{True. } f(n) \text{ grows at least as fast as } g(n)
  • f(n)=o(g(n))→False. o(g(n)) would mean that f(n) grows slower than g(n).f(n) = o(g(n)) \rightarrow \text{False. } o(g(n)) \text{ would mean that } f(n) \text{ grows slower than } g(n).
  • f(n)=ω(g(n))→True. f(n) grows strictly faster than g(n)f(n) = \omega(g(n)) \rightarrow \text{True. } f(n) \text{ grows strictly faster than } g(n)