1.2.2 Examples

• Let f(n) = n² + n + 5. Then

  -

  f(n) is O(n²)

  -

  f(n) is O(n³)

  -

  f(n) is not O(n)

• Let f(n) = 3ⁿ

  -

  f(n) is O(4ⁿ)

  -

  f(n) is not O(2ⁿ)

• If f₁(n) is O(g₁(n)) and f₂(n) is O(g₂(n)), then

  -

  f₁(n) + f₂(n) is O(max(g₁(n), g₂(n)))