跳到主要内容位置

Big O Notation and Asymptotic Analysis

Basic Rules​

  • OO (big-oh): upper bound
  • Ω\Omega (big-omega): lower bound
  • Θ\Theta (theta): average bound

Example 1: Big-O Notation​

Definition: The function f(n)=O(g(n))f(n) = O(g(n)) if there exist constants cc and n0n_0 such that:

f(n)≤c⋅g(n) for all n≥n0f(n) \leq c \cdot g(n) \text{ for all } n \geq n_0

For f(n)=2n+3f(n) = 2n + 3:

A simple approach is to multiply by nn:

f(n)=2n+3≤2n+3n=5n for n≥1f(n) = 2n + 3 \leq 2n + 3n = 5n \text{ for } n \geq 1

Therefore, f(n)=O(n)f(n) = O(n)

We can also show:

f(n)=2n+3≤2n2+3n2=5n2 for n≥1f(n) = 2n + 3 \leq 2n^2 + 3n^2 = 5n^2 \text{ for } n \geq 1

So f(n)=O(n2)f(n) = O(n^2) is also true.

Asymptotic Growth Rates​

From slowest to fastest growing:

1<log⁡n<n<n<nlog⁡n<n2<n3<…<2n<3n<…<nn1 < \log n < \sqrt{n} < n < n\log n < n^2 < n^3 < \ldots < 2^n < 3^n < \ldots < n^n

For f(n)=O(n)f(n) = O(n):

  • Functions larger than nn (like nlog⁡nn\log n) can satisfy the O(n)O(n) upper bound
  • Functions smaller than nn (like n\sqrt{n}) can satisfy the Ω(n)\Omega(n) lower bound

Note that:

f(n)=O(n)  ⟹  f(n)=O(n2)  ⟹  f(n)=O(2n)f(n) = O(n) \implies f(n) = O(n^2) \implies f(n) = O(2^n)

Example 2: Big-Omega Notation​

Definition: The function f(n)=Ω(g(n))f(n) = \Omega(g(n)) if there exist constants cc and n0n_0 such that:

f(n)≥c⋅g(n) for all n≥n0f(n) \geq c \cdot g(n) \text{ for all } n \geq n_0

For our function f(n)=2n+3f(n) = 2n + 3:

  • f(n)f(n) cannot be written as Ω(log⁡n)\Omega(\log n)
  • The most similar bound is Ω(n)\Omega(n)

Note that:

f(n)=Ω(n)  ⟹  f(n)=Ω(log⁡n)  ⟹  f(n)=Ω(n)  ⟹  f(n)=Ω(1)f(n) = \Omega(n) \implies f(n) = \Omega(\log n) \implies f(n) = \Omega(\sqrt{n}) \implies f(n) = \Omega(1)

Example 3: Theta Notation​

Definition: The function f(n)=Θ(g(n))f(n) = \Theta(g(n)) if there exist constants c1c_1, c2c_2, and n0n_0 such that:

c1⋅g(n)≤f(n)≤c2⋅g(n) for all n≥n0c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \text{ for all } n \geq n_0

For f(n)=2n+3f(n) = 2n + 3:

1⋅n≤2n+3≤5⋅n for n≥31 \cdot n \leq 2n + 3 \leq 5 \cdot n \text{ for } n \geq 3

Where 1⋅n1 \cdot n is c1⋅g(n)c_1 \cdot g(n) and 5⋅n5 \cdot n is c2⋅g(n)c_2 \cdot g(n)

Therefore, f(n)=Θ(n)f(n) = \Theta(n)

Example 4​

For f(n)=2n2+3n+4f(n) = 2n^2 + 3n + 4:

Upper bound:

f(n)=2n2+3n+4≤2n2+3n2+4n2=9n2 for n≥1f(n) = 2n^2 + 3n + 4 \leq 2n^2 + 3n^2 + 4n^2 = 9n^2 \text{ for } n \geq 1

Therefore, f(n)=O(n2)f(n) = O(n^2)

Lower bound:

f(n)=2n2+3n+4≥1⋅n2 for n≥1f(n) = 2n^2 + 3n + 4 \geq 1 \cdot n^2 \text{ for } n \geq 1

Therefore, f(n)=Ω(n2)f(n) = \Omega(n^2)

Since f(n)=O(n2)f(n) = O(n^2) and f(n)=Ω(n2)f(n) = \Omega(n^2), we have f(n)=Θ(n2)f(n) = \Theta(n^2)

Example 5​

For f(n)=n2log⁡nf(n) = n^2\log n:

n2log⁡n≤f(n)=n2log⁡n≤10n2log⁡nn^2\log n \leq f(n) = n^2\log n \leq 10n^2\log n

Therefore, f(n)=O(n2log⁡n)f(n) = O(n^2\log n) and f(n)=Ω(n2log⁡n)f(n) = \Omega(n^2\log n)

Thus, f(n)=Θ(n2log⁡n)f(n) = \Theta(n^2\log n)

Example 6​

For f(n)=n!f(n) = n!:

1≤n!=n⋅(n−1)⋅...⋅1≤n⋅n⋅...⋅n=nn1 \leq n! = n \cdot (n-1) \cdot ... \cdot 1 \leq n \cdot n \cdot ... \cdot n = n^n

Therefore, f(n)=O(nn)f(n) = O(n^n) and f(n)=Ω(1)f(n) = \Omega(1)

For n!n!, we cannot establish a tight Θ\Theta bound using simple functions.

Example 7​

For f(n)=log⁡(n!)f(n) = \log(n!):

log⁡(1)≤log⁡(n!)≤log⁡(nn)=nlog⁡n\log(1) \leq \log(n!) \leq \log(n^n) = n\log n

Therefore, f(n)=O(nlog⁡n)f(n) = O(n\log n) and f(n)=Ω(1)f(n) = \Omega(1)

For log⁡(n!)\log(n!), a tight Θ\Theta bound would require more analysis.