Skip to main content

Big-O, Omega, and Theta Bound Growth, Not Time

What This Concept Is​

Asymptotic notation describes how a function grows as $n$ gets large. It is not a measurement of seconds, not a prediction of wall-clock time, and not a statement about small inputs. It is a statement about the shape of a cost function once you strip constants and low-order terms.

Three bounds carry almost all algorithm work:

  • $f(n) = O(g(n))$ iff there exist constants $c > 0$ and $n_0$ such that $0 \le f(n) \le c \cdot g(n)$ for all $n \ge n_0$. Upper bound. "$f$ grows no faster than $g$."
  • $f(n) = \Omega(g(n))$ iff there exist constants $c > 0$ and $n_0$ such that $0 \le c \cdot g(n) \le f(n)$ for all $n \ge n_0$. Lower bound. "$f$ grows at least as fast as $g$."
  • $f(n) = \Theta(g(n))$ iff both $O(g(n))$ and $\Omega(g(n))$ hold. Tight bound. "$f$ and $g$ share a growth shape."

The constants $c$ and $n_0$ exist precisely to swallow hardware speed, lower-order terms, and startup effects. They are witnesses, not magic: a claim of $O(n^2)$ is unfinished until you can produce $c$ and $n_0$ that make the inequality hold.

Two fine-grained siblings round out the vocabulary. Little-$o$ means strictly smaller: $f(n) = o(g(n))$ iff $\lim_{n\to\infty} f(n)/g(n) = 0$. Little-$\omega$ is the strict lower-bound dual. We rarely need them for design, but they matter whenever you want to say "$n$ is truly smaller than $n \log n$," not just "no larger."

Asymptotic notation is also used in three distinct places: the input size domain (worst, average, best), the resource dimension (time, space, bit operations, cache misses, network round-trips), and the case you have named. Always say which. "Binary search is $O(\log n)$" silently means "time, worst case, comparisons on a sorted array."

A final semantic wrinkle: the notation $f(n) = O(g(n))$ is an abuse of the equals sign. Read it as "$f(n) \in O(g(n))$" - membership in a set of functions. You cannot derive $O(g(n)) = f(n)$; the relation is not symmetric. Nesting ($2n + O(n) = O(n)$) reads left-to-right: the left side contains an anonymous function bounded by $n$, and the whole expression is declared bounded by $n$. CLRS §3.2 spells out the convention; CS-theory papers lean on it heavily.

Why It Matters Here​

Every later analysis in the semester leans on these definitions:

  • "Binary search is $O(\log n)$" is a claim about a dominance relation, not a stopwatch reading.
  • "Mergesort is $\Theta(n \log n)$" means both its best and worst cases share that shape, so no input pattern makes it asymptotically faster or slower.
  • "Insertion sort is $\Omega(n^2)$ in the worst case" rules out any $c \cdot n \log n$ bound on adversarial input - no cleverer analysis will rescue it.
  • "Comparison-based sorting is $\Omega(n \log n)$" (the decision-tree lower bound from CLRS §8.1) is a statement about every possible algorithm, not one implementation.

If you conflate $O$ with "running time," you will misread entire algorithm families, invent non-existent speedups, and be unable to talk with anyone about tail behavior, competitive ratios, or approximation guarantees in later modules.

Concrete Example​

Example 1 (polynomial). Let $f(n) = 3n^2 + 10n + 7$. Claim: $f(n) = \Theta(n^2)$.

Upper bound: pick $c = 20$, $n_0 = 1$. For $n \ge 1$, $3n^2 + 10n + 7 \le 3n^2 + 10n^2 + 7n^2 = 20n^2$.

Lower bound: for $n \ge 1$, $f(n) \ge 3n^2$, so $c = 3$, $n_0 = 1$ works.

Both bounds hold, so $f(n) = \Theta(n^2)$. Note that $f(n) = O(n^3)$ is technically true but loose; $\Theta$ is what you want whenever you can get it, because it forbids anyone from tightening the bound further.

Example 2 (mixed). Is $f(n) = n \log n + 100n$ in $\Theta(n \log n)$? For $n \ge 2^{100}$, $\log n \ge 100$, so $100n \le n \log n$ and $f(n) \le 2n \log n$. Hence $f = O(n \log n)$. Also $f \ge n \log n$ for $n \ge 2$, so $f = \Omega(n \log n)$. Tight.

Example 3 (exponentials separate). $2^{n+1} = 2 \cdot 2^n = O(2^n)$: take $c = 2$. But $2^{2n} = (2^n)^2$ is not $O(2^n)$, because no constant $c$ satisfies $(2^n)^2 \le c \cdot 2^n$ for all large $n$. Constants never change the exponent.

Example 4 (limit form as shortcut). Claim: $n \log n = o(n^{1.01})$. Compute

$$\lim_{n\to\infty} \frac{n \log n}{n^{1.01}} = \lim_{n\to\infty} \frac{\log n}{n^{0.01}} = 0$$

by L'Hopital (numerator derivative $1/n$, denominator derivative $0.01 n^{-0.99}$, ratio $\to 0$). Limit is $0$, so little-$o$ holds. Any polynomial factor, however tiny the exponent, dominates every polylog.

Common Confusion / Misconceptions​

  • "Big-O is worst case." No. Big-O is an upper bound on a chosen function. You can apply it to best, average, worst, amortized, or expected cost separately. "Quicksort is $O(n \log n)$ expected" and "quicksort is $O(n^2)$ worst case" are both valid and distinct.
  • "Bigger Big-O means slower." Only for large $n$. On $n = 8$, a $O(n^2)$ implementation can beat a $O(n \log n)$ one with painful constants. The notation strips constants deliberately; never quote it as if it predicted wall-clock time on small inputs.
  • "$\Theta$ and $O$ are the same when they both exist." $\Theta$ is strictly stronger: it asserts a matching lower bound. Saying "heapsort is $O(n^2)$" is true (and uninformative). Saying "heapsort is $\Theta(n \log n)$" is the claim that excludes any tighter analysis.
  • "Asymptotic ignores everything, so it's useless for real engineering." Asymptotic classification is the primary filter for design decisions. Constants refine the choice within a class (see concept 17). One does not replace the other.
  • "$f = O(g)$ and $g = O(f)$, therefore $f = g$." They share a $\Theta$-class; they are not equal as functions. $3n$ and $n + \log n$ are both $\Theta(n)$ and differ by an unbounded amount.
  • "If $f = O(g)$ then eventually $f < g$." Only up to a constant: $f \le c \cdot g$ for some $c$ that might be 1000. Asymptotics never promised pointwise dominance.

How To Use It​

For every claim $f(n) = O(g(n))$:

  1. Identify the dominant term of $f$ (ignore coefficients and lower-order terms).
  2. Pick $g(n)$ to match that dominant term.
  3. If nontrivial, name $c$ and $n_0$ explicitly so the inequality is mechanically verifiable.
  4. Strengthen to $\Theta$ whenever the lower bound is equally tight; otherwise, state why only $O$ is known.
  5. State the case (worst, average, best, amortized) and the resource (time, space, cache misses, messages).
  6. Sanity check via the limit form: $f = O(g)$ iff $\limsup f/g < \infty$; $f = \Theta(g)$ iff $0 < \lim f/g < \infty$.
  7. Run two sample sizes (e.g., $n$ and $2n$) and confirm the ratio of empirical costs matches the predicted growth. Big disagreement means the analysis is wrong, the constants are enormous, or the input is outside the asymptotic regime.
  8. Never compose asymptotic bounds multiplicatively without checking independence: an outer loop that is $O(n)$ around an inner call that is $O(n)$ on unrelated inputs gives $O(n^2)$, but if the inner call's cost depends on loop-accumulated state (a hash table whose size grows), the analysis is different (see concept 2 and concept 4).

Reserve $O$ for statements of the form "no worse than" and $\Theta$ for "growth is exactly this shape up to constants."

Memorize this growth hierarchy (each strictly dominates the previous for large $n$):

$$1 \prec \log\log n \prec \log n \prec \sqrt{n} \prec n \prec n \log n \prec n^2 \prec n^3 \prec 2^n \prec n! \prec n^n.$$

Recognizing which tier an algorithm lives in is the day-to-day use of this concept. When someone claims "a factor of $\log n$ is not a big deal," check their $n$: at $n = 10^9$, $\log_2 n \approx 30$ - that 30x can decide whether a request fits in a p99 budget.

Transfer / Where This Shows Up Later​

  • S1 M2 (counting) and S1 M3 (probability) supplied the combinatorial and probabilistic tools you now use to sum cases and compute expected values; asymptotic notation is where those sums become usable (a size-$\binom{n}{2}$ count becomes $\Theta(n^2)$).
  • S1 M5 (problem solving) framed "estimate before you optimize." Asymptotic bounds are the estimate.
  • S4 (systems) reuses this vocabulary for cache-complexity analysis ($O(n/B)$ block transfers) and for the memory hierarchy's asymptotic cost model.
  • S5 (OS / scheduling) states scheduler fairness and queueing guarantees in asymptotic terms: $O(\log n)$ per context switch, $\Theta(1)$ amortized enqueue, tail bounds in $O(\log n)$ on a balanced tree of runnable tasks.
  • S6 (databases) expresses query planner cost models, LSM compaction write amplification, and CAP-aware tail-latency promises asymptotically.
  • S7 (architecture) writes fitness functions in terms of asymptotic targets: "p99 latency stays $O(\log n)$ in catalog size."
  • S8 (distributed) uses the same language for capacity planning ("doubling traffic takes us from $O(n)$ to $O(n \log n)$ work") and for load-shaping back-pressure.

Every "this scales" claim anywhere in the degree routes through this page.

Later-module anchors where these notations recur:

  • S2 M2 (sorting and searching). Every comparison-based sort's $\Omega(n \log n)$ lower bound and counting-sort's $\Theta(n + k)$ contrast live here.
  • S2 M3 (graph algorithms). BFS/DFS are $\Theta(V + E)$; Dijkstra with a binary heap is $O((V+E) \log V)$; tightness of these bounds is proved with the same definitions as above.
  • S2 M4 (dynamic programming). DP runtime is (states) $\times$ (transitions per state); asymptotic analysis is how you state and verify that product.
  • S2 M5 (advanced structures). Union-find amortizes to $O(\alpha(n))$ per operation - a concrete use of the little-$o$ cousin you met here.

Check Yourself​

  1. Give an example where $f(n) = O(g(n))$ but not $\Theta(g(n))$, and explain why the lower bound fails.
  2. Why is $2^{n+1} = O(2^n)$ but $2^{2n}$ is not?
  3. What does it mean to say an algorithm is $\Omega(n \log n)$ in the worst case, and why is that sometimes more interesting than a matching $O$ bound?
  4. Your colleague writes "our cache lookup is $O(1)$" in a design doc. Name three questions you would ask before accepting the claim.
  5. Under what conditions is $f(n) + g(n) = \Theta(\max(f, g))$? Prove it.
  6. True or false, with justification: $n^{\log n}$ is $O(2^n)$. (Hint: take logs.)
  7. Why is "$n^{1+\epsilon}$ dominates $n \log^k n$ for any fixed $k$ and any $\epsilon > 0$" a statement about limits, not constants?

Mini Drill or Application​

For each pair, decide whether the first is $O$, $\Omega$, $\Theta$, or none relative to the second. Justify with constants or a limit argument.

  1. $f(n) = n \log n$, $g(n) = n^{1.5}$
  2. $f(n) = 100 n + 50$, $g(n) = n$
  3. $f(n) = n!$, $g(n) = 2^n$
  4. $f(n) = \log(n^5)$, $g(n) = \log n$
  5. $f(n) = \sqrt{n}$, $g(n) = \log n$
  6. $f(n) = 2^{\log_2 n}$, $g(n) = n$
  7. $f(n) = n^{\log_2 3}$, $g(n) = n^{1.6}$ (think Karatsuba vs $n^{1.6}$)
  8. Implementation drill. Write pseudocode for is_big_oh(f_table, g_table, c, n0) that checks the $O$ definition on a sampled table of values of $f$ and $g$, and returns FAIL with the first offending $n$ if the inequality is violated. Complexity: $\Theta(|\text{table}|)$. This is how you sanity-check claims numerically before committing to a proof.

Read This Only If Stuck​