Big O Notation

Jr Codex DSA Notes

Level: Beginner Prerequisites: Chapter 1 Time to complete: ~25 minutes

Table of Contents

1. What Big O Actually Measures
2. Common Complexity Classes
3. O(1) — Constant Time
4. O(log n) — Logarithmic Time
5. O(n) — Linear Time
6. O(n log n) — Linearithmic Time
7. O(n²) — Quadratic Time
8. O(2ⁿ) and O(n!) — Exponential & Factorial Time
9. Growth Rate Intuition
10. Summary & Next Steps

1. What Big O Actually Measures

Big O notation describes how an algorithm's runtime (or memory use) grows as input size grows — not the exact number of seconds it takes on your laptop. It answers: "If I double the input, roughly how much more work does this do?"

n conventionally represents the input size (length of a list, number of nodes, etc.). Big O describes the shape of the growth curve as n gets large — it deliberately ignores machine speed, constant setup costs, and small-n behavior, because those don't tell you how the algorithm will hold up as data grows.

Big O answers:  "As n → very large, how does runtime scale?"
Big O ignores:  Exact seconds, hardware, small constant overhead

2. Common Complexity Classes

From best to worst (for large n):

3. O(1) — Constant Time

The operation takes the same amount of time regardless of input size.

def get_first(items):
    return items[0]      # O(1) — one step, no matter how big `items` is

4. O(log n) — Logarithmic Time

The work needed shrinks by a fraction (usually half) each step. Doubling the input adds only one more step, not double the steps.

def binary_search(sorted_items, target):
    low, high = 0, len(sorted_items) - 1
    while low <= high:
        mid = (low + high) // 2
        if sorted_items[mid] == target:
            return mid
        elif sorted_items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
    # Each iteration eliminates HALF the remaining items — O(log n)

With 1,000,000 items, linear search might take 1,000,000 steps in the worst case; binary search takes at most ~20. That gap is why O(log n) algorithms are prized (covered fully in Module 3).

5. O(n) — Linear Time

Work grows in direct proportion to input size — one pass over the data.

def contains(items, target):
    for item in items:        # up to n iterations
        if item == target:
            return True
    return False

6. O(n log n) — Linearithmic Time

Common in efficient sorting algorithms: the data is repeatedly split (the log n part) and each split does linear work to combine results (the n part). Merge sort and quick sort (Module 3) are the canonical examples — this is the best achievable complexity for general-purpose comparison-based sorting.

7. O(n²) — Quadratic Time

A loop nested inside another loop over the same input — for every item, you do roughly n more work.

def has_duplicate_pair(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):   # nested loop over the same list
            if items[i] == items[j]:
                return True
    return False
    # n items, each compared against ~n others → O(n²)

Quadratic algorithms are fine for small n (dozens, hundreds) but become impractical fast — 10x the input means ~100x the work.

8. O(2ⁿ) and O(n!) — Exponential & Factorial Time

These appear when an algorithm explores every possible combination or ordering:

def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
    # Each call spawns 2 more calls → roughly O(2ⁿ) — becomes unusable past n≈40

Module 10 (Dynamic Programming) exists largely to turn algorithms like this into O(n) or O(n²) ones.

9. Growth Rate Intuition

For n = 20:

O(log n)   ≈ 4 operations
O(n)       ≈ 20 operations
O(n log n) ≈ 86 operations
O(n²)      ≈ 400 operations
O(2ⁿ)      ≈ 1,048,576 operations
O(n!)      ≈ 2,432,902,008,176,640,000 operations

At small n, the difference feels academic. At real-world scale, it's the difference between a response in milliseconds and a program that never finishes. Internalizing this table is the single highest-value thing to take from this chapter.

10. Summary & Next Steps

Key Takeaways

• Big O describes how runtime scales with input size, not exact speed on any one machine.
• Memorize the ordering: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).
• A nested loop over the same input is a strong signal of O(n²); a loop that halves its search space each step is a strong signal of O(log n).
• The gap between complexity classes explodes at scale — an O(n²) algorithm that's "fine" at n=100 may be unusable at n=1,000,000.

Concept Check

1. Why does Big O ignore constant factors and machine speed?
2. What pattern in code usually signals O(n²)?
3. Why is O(2ⁿ) naive Fibonacci considered impractical for even moderately sized n?

Next Chapter

→ Chapter 3: Time Complexity Analysis

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index