C++UCS301
Algorithm AnalysisC++17

Big-O, Ω & Θ

Asymptotic notation describes the eventual growth of a function while ignoring constants and lower-order terms.

What to understand

  • Upper, lower, and tight bounds
  • Dropping constants
  • Dominant terms
  • Common growth families

Remember this

  1. 1O is an upper bound
  2. 2Ω is a lower bound
  3. 3Θ is a tight bound
  4. 4O(2n) = O(n)

Detailed notes

Big-O, Big-Ω, and Big-Θ compare functions after some sufficiently large input size. Formal definitions use constants to bound one function above, below, or on both sides by another function.

The notation hides constant factors and lower-order terms because growth dominates at scale. It does not mean constants never matter; it means asymptotic class and practical constants answer different questions.

How it works

  1. 1Expand the operation-count function T(n).
  2. 2Drop constant multipliers and lower-order terms.
  3. 3Use O for an eventual upper bound and Ω for a lower bound.
  4. 4Use Θ only when matching upper and lower bounds are known.

Where it is used

  • Communicating performance guarantees
  • Comparing algorithms across machines
  • Bounding loops, recurrences, and data-structure operations

Common mistakes

  • Saying O(n²) is always slower than O(n) for every n
  • Treating Big-O as an exact running time
  • Calling every worst-case bound Θ without proving a lower bound

C++ implementation

C++17 reference
main.cpp

Three different growth rates

These loops perform constant, logarithmic, and quadratic work respectively.

// O(1)
cout << values[0];

// O(log n): i doubles each iteration
for (int i = 1; i < n; i *= 2)
    cout << i << ' ';

// O(n^2): every ordered pair
for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
        process(i, j);
11 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.