Bounds
\(O\) may be loose. \(\Theta\) is the one you report when you actually counted.
We write \(f(N) = O(g(N))\) even though \(O(g)\) is a set. The equals sign means “is a member of.”
\(f(N) = O(g(N))\) means there exist constants \(c > 0\) and \(N_0 > 0\) such that \(0 \le f(N) \le c\,g(N)\) for every \(N \ge N_0\). Upper bound. It may be sloppy: \(2N = O(N^2)\) is true.
\(f(N) = \Omega(g(N))\) flips the inequality. Lower bound. Also allowed to be loose.
\(f(N) = \Theta(g(N))\) means both. Same growth rate.
| Symbol | Limit test | Plain English |
|---|---|---|
| \(f = o(g)\) | \(\lim f/g = 0\) | strictly slower, no tie |
| \(f = O(g)\) | \(f/g\) stays bounded | no faster, tie allowed |
| \(f = \Theta(g)\) | \(f/g\) tends to a positive constant | tied |
| \(f = \Omega(g)\) | \(f/g\) stays at least some positive constant | no slower, tie allowed |
| \(f = \omega(g)\) | \(\lim f/g = \infty\) | strictly faster, no tie |
Little-o, formally: for every \(c > 0\), not merely some \(c\), there is an \(N_0\) past which \(f(N) < c\,g(N)\). That is why \(2N^2 \neq o(N^2)\). The ratio tends to 2, not to 0.
The leading term can lose the first lap
\(T(N) = 7N^3 + 100N^2 + 4\) is \(\Theta(N^3)\). At \(N = 10\), \(7N^3 = 7000\) and \(100N^2 = 10000\). The “lower-order” term is still winning. They cross when \(7N = 100\), so \(N \approx 14.3\). From \(N = 15\) upward the cubic term leads, and the gap only grows. \(\Theta\) describes the far end of the track.
That is also why a \(\Theta(N^2)\) algorithm can beat a \(\Theta(N \log N)\) algorithm on a tiny input. For \(N = 10^6\) you take the slower-growing one.
Change of base is a constant, and constants die inside \(\Theta\). \(\log_2 N\), \(\ln N\), and \(\log_{10} N\) are the same class.
| Class | Replacing \(N\) by \(2N\) |
|---|---|
| \(\Theta(1)\) | stays the same |
| \(\Theta(\log N)\) | adds about 1 |
| \(\Theta(N)\) | multiplies by 2 |
| \(\Theta(N \log N)\) | a bit more than 2, and the extra shrinks |
| \(\Theta(N^2)\) | multiplies by 4 |
| \(\Theta(N^3)\) | multiplies by 8 |
| \(\Theta(2^N)\) | squares the old amount |
| \(N\) | \(\log_2 N\) | \(N\) | \(N\log_2 N\) | \(N^2\) | \(2^N\) |
|---|---|---|---|---|---|
| 10 | 3.3 | 10 | 33 | 100 | 1,024 |
| 20 | 4.3 | 20 | 86 | 400 | about \(10^6\) |
| 40 | 5.3 | 40 | 213 | 1,600 | about \(10^{12}\) |
Try this
True or false: \(3N\log N = o(N^2)\), and \(2N^2 = o(N^2)\).
Show the answer
The first is true, because \(3\log N / N \to 0\). The second is false. The ratio tends to 2, so they are \(\Theta\) of each other. \(2N^2\) is \(O(N^2)\) and not \(o(N^2)\).