Big-O is the language interviewers and contest setters use to talk about speed. It answers one question: as the input grows, how does the work grow?

What you’ll learn

• What Big-O, Big-Omega, and Big-Theta actually mean.
• The complexity hierarchy and how to read it off code.
• Best vs average vs worst case.
• Amortized analysis (why list.appendlist.append is ”$O(1)$” despite resizing).
• The Python constant-factor reality that decides TLE.

The core idea

Big-O describes an upper bound on growth, ignoring constants and lower-order terms. Formally, $f(n) = O(g(n))$ if there exist constants $c > 0$ and $n_0$ such that:

So $3n^2 + 5n + 100 = O(n^2)$ — the $n^2$ term dominates, constants drop.

Two companions complete the picture:

• $\Omega(g(n))$ — a lower bound (the work is at least this).
• $\Theta(g(n))$ — a tight bound (upper and lower).

Watch the growth rates race

Small inputs hide everything — every algorithm looks fast. The gap explodes as $n$ grows. This is why $O(n \log n)$ beats $O(n^2)$ so decisively on large data:

The hierarchy (fastest to slowest)

Reading complexity off code

Count the loops and how the input drives them.

# O(1) — no loop over input
def first(nums):
    return nums[0] if nums else None
 
# O(n) — one pass
def total(nums):
    s = 0
    for x in nums:          # runs n times
        s += x
    return s
 
# O(n^2) — loop inside a loop over the same data
def any_pair_sums_zero(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == 0:
                return True
    return False
 
print(first([9, 2]), total([1, 2, 3]), any_pair_sums_zero([3, -3, 5]))

# O(1) — no loop over input
def first(nums):
    return nums[0] if nums else None
 
# O(n) — one pass
def total(nums):
    s = 0
    for x in nums:          # runs n times
        s += x
    return s
 
# O(n^2) — loop inside a loop over the same data
def any_pair_sums_zero(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == 0:
                return True
    return False
 
print(first([9, 2]), total([1, 2, 3]), any_pair_sums_zero([3, -3, 5]))

Best, average, worst

The same algorithm can have different costs depending on the input.

• Best case — luckiest input (e.g., target is the first element).
• Worst case — the input interviewers care about most.
• Average case — expected over random inputs.

Linear search: best $O(1)$ (found first), worst $O(n)$ (found last / absent).

Amortized analysis

Some operations are occasionally expensive but cheap on average over a sequence. list.appendlist.append is the classic: usually $O(1)$, but when the underlying array is full Python allocates a bigger one and copies everything ($O(n)$). Because resizes double capacity, those costs spread out to amortized $O(1)$.

The Python constant-factor reality

Big-O drops constants — but on a real judge, constants decide TLE. Python is ~10–100× slower per operation than C++. A rough safe budget per second:

  graph LR
    A["n up to 1e8
O(n) only, tight loops"] --> B["n up to 1e6-1e7
O(n) / O(n log n)"]
    B --> C["n up to 1e4
O(n^2) ok"]
    C --> D["n up to ~20
O(2^n) ok"]
    D --> E["n up to ~11
O(n!) ok"]

We cover concrete TLE-beating tricks (fast I/O, stdlib, PyPy) in Phase 2: Python for DSA & CP.

Practice

Drill 1 — name the complexity. Complete the function so it runs in $O(n)$, not $O(n^2)$: sum every element using a single pass.

Drill 2 — pick the fast structure. Counting frequencies with a nested scan is $O(n^2)$. A dictdict makes it $O(n)$. Fill the blank.

Recap

• Big-O = growth of work vs input; drop constants and lower-order terms.
• Know the hierarchy cold: $O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n) < O(n!)$.
• Sequential adds, nested multiplies; keep the dominant term.
• Amortized cost spreads rare expensive ops across many cheap ones.
• In Python, constants matter — use $n$ to guess the intended complexity.

Next: Recurrences & the Master Theorem — complexity for divide-and-conquer.