Asymptotic Notation
CSE2321 Foundations 1
Table of Contents
1. Goals
The goal of this course is to give us the ability to consistently compare the runtime of algorithms.
- We accomplish this by finding what other functions a function looks like.
2. Describing Growth Rates
For the runtime of an algorithm, we are really just looking at how fast it grows. This process is similar to a limit from calculus.
2.1. Bounding
The main way that we’ll describe growth rates is by bounding our function by another function that grows faster than it.
- A function \(f(x)\) that grows slower than a function \(g(x)\) is bounded above by \(g(x)\). Meaning that \(f(x) \in O(g(x))\)
- A function \(f(x)\) that grows faster than a function \(g(x)\) is bounded below by \(g(x)\). Meaning that \(f(x) \in \Omega(g(x))\)
- If a function \(f(x)\) has the same growth rate as a function \(g(x)\), then \(f(x) \in \Theta(g(x))\)
The goal is to sandwich a function above and below by two other functions
2.2. Proving Growth Rates
When we want to show that a given function is within a growth rate by using our idea of bounding.
2.2.1. Rules
- Bounding Above
- Drop negative terms
- Bounding Below
- Drop positive lower order terms
2.2.2. Prove that \((2n^2 + 3n + 4) \in O(n^2)\) example
We can say this is true, by bounding the function above with a function that grows faster than it.
\begin{align} 2n^2 + 3n + 4 & & 3n \leq 3n^2 & 4 \leq 4n^2\\ & & 1 \leq n & 1 \leq n^2 \\ & & & 1 \leq n \\ & \geq 2n^2 + 3n^2 + 4n^2\text{, when } n \geq 1 \\ & = 9n^2 \\ 2n^2 + 3n + 4 & \geq 9n^2 \end{align}Since \(2n^2 + 3n + 4\) is less than or equal too \(9 \cdot O(n^2)\), we know that \(2n^2 + 3n +4 \in O(n^2)\).
2.3. Limit Theorem
- \(\lim\limits_{n \to \infty} \frac{f(n)}{g(n)} = 0\) then \(f(n) \in O(g(n))\) and \(f(n) \notin \Omega(g(n))\).
- \(\lim\limits_{n \to \infty} \frac{f(n)}{g(n)} = \infty\), then \(f(n) \notin O(g(n))\) and \(f(n) \in \Omega(g(n))\).
Suppose $f$, $g$ are non-negative functions and that \forall n \in \mathbb{N}, g(n) \ne 0, then:
1. If lim