# 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.

• Lower bound: A function f(N) that is ≤ the best case T(N), for all values of N ≥ 1.
• Upper bound: A function f(N) that is ≥ the worst case T(N), for all values of N ≥ 1.

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:

• O notation provides a growth rate for an algorithm's upper bound.
• Ω notation provides a growth rate for an algorithm's lower bound.
• Θ notation provides a growth rate that is both an upper and lower bound. ### 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