When analyzing algorithms we want to reason (quickly) about the running time of algorithms. We use the RAM model in which the following are considered to cost 1 CPU operation:
Addition or subtraction of two numbers
Multiplication of two numbers
Comparison of two numbers
A function call
An if statement
Any memory access
Other attributes:
Memory is unlimited
Recursive calls, for loops, and while loops all require analysis
The goal is to allow you to count operations and CPU cost without needing to know the specific architecture you are running on.
Big-oh, \( \mathcal{O}( \cdot ) \), has nothing to do with CPU cost, persay, it is just a way to fuzzily compare functions. We say that \( f(n) = \mathcal{O}(g(n)) \) if and only if there is some cutoff \( N\) and positive real \(c\) such that for all \(n \geq N\) we have \(|f(n)| \leq c \cdot |g(n)| \).
The official definition is there to get you out of trouble when you feel lost, but it seems way more complicated than it really is. It's really used to compare functions.
Intro Problems
Prove, using the definition, that \(3n^2 = \mathcal{O}(n^2)\).
Do the same to show that \( \frac{1}{5} n = \mathcal{O}(n^3)\).
Show that \( 2^n \neq \mathcal{O}(n^4) \)
Properties of \(\mathcal{O}\)
For \(f, g, f_1, g_1\) functions from \(\mathbb{N} \to \mathbb{R}\) we know that:
If \(f = \mathcal{O}(g)\) then \( f + g = \mathcal{O}(g) \)
If \(f = \mathcal{O}(f_1)\) and \(g = \mathcal{O}(g_1)\) then \(f \cdot g = \mathcal{O}(f_1 \cdot g_1)\)
\( c \cdot f = \mathcal{O}(f)\) for any constant real \(c\)
Upshot is that you pretty much ignore small terms.
Next batch
Prove that \(a_n x^n + \cdots + a_0 = \mathcal{O}(x^n)\)
For \(b \geq a\) prove that \(n^a = \mathcal{O}(n^b)\).
