2.5 Growth of functions and complexity

Upper and lower bounds

An algorithm with runtime complexity T(N) has a lower bound and an upper bound.

Ex: An algorithm with best case runtime T(N)=7N+36 and worst case runtime T(N) = 3N² + 10N + 17, has a lower bound f(N) = 7N and an upper bound f(N) = 30N². These lower and upper bounds provide a general picture of the runtime, while using simpler functions than the exact runtime

Upper and lower bounds in the context of runtime complexity

In strict mathematical terms, upper and lower bounds do not relate to best or worst case runtime complexities. In the context of algorithm complexity analysis, the terms are often used to collectively bound all runtime complexities for an algorithm. Therefore, the terms are used in this section such that the upper bound is ≥ the worst case T(N) and the lower bound is ≤ the best case T(N).

Activity 1: Upper and lower bounds.

Suppose an algorithm's best case runtime complexity is T(N) = 3N + 6, and the algorithm's worst case runtime is T(N) = 5N² + 7N.

  1. Which function is a lower bound for the algorithm?
    5N²
    5N
    3N


  2. Which function is an upper bound for the algorithm?
    12N²
    5N²
    7N


  3. 5N² + 7N is an upper bound for the algorithm.
    True
    False


  4. 3N + 6 is a lower bound for the algorithm.
    True
    False


Growth rates and asymptotic notations

An additional simplification can factor out the constant from a bounding function, leaving a function that categorizes the algorithm's growth rate. Ex: Instead of saying that an algorithm's runtime function has an upper bound of 30N², the algorithm could be described as having a worst case growth rate of N^2. Asymptotic notation is the classification of runtime complexity that uses functions that indicate only the growth rate of a bounding function. Three asymptotic notations are commonly used in complexity analysis:

image1

Activity 2: Asymptotic notations.

Suppose T(N) = 2N² + N + 9.

  1. T(N) = O(N²)
    True
    False


  2. T(N) = Ω(N²)
    True
    False


  3. T(N) = Θ(N³)
    True
    False


  4. T(N) = O(N³)
    True
    False


  5. T(N) = Ω(N³)
    True
    False