Time Complexity Analysis

Jr Codex DSA Notes

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

The Core Technique: Count the Operations
Sequential Statements Add
Loops Multiply
Nested Loops
Loops That Don't Depend on Each Other
Dropping Constants and Lower-Order Terms
Function Calls Inside Loops
Summary & Next Steps

1. The Core Technique: Count the Operations

Analyzing time complexity is mechanical once you know the rules: count how many times the "basic operation" (a comparison, an assignment, an arithmetic step) runs, expressed as a function of n, then simplify to Big O using the rules below.

2. Sequential Statements Add

def example(items):
    print(items[0])       # O(1)
    total = sum(items)    # O(n)
    print(total)            # O(1)
    # Total: O(1) + O(n) + O(1) = O(n) — the largest term dominates

When steps run one after another (not nested), you add their complexities, then keep only the largest term.

3. Loops Multiply

A single loop over n items, doing constant work each iteration, is O(n):

def print_all(items):
    for item in items:      # runs n times
        print(item)         # O(1) work each time
    # n × O(1) = O(n)

4. Nested Loops

Nested loops multiply. A loop inside a loop, each running n times, gives O(n) × O(n) = O(n²):

def print_pairs(items):
    for a in items:            # n iterations
        for b in items:        # n iterations, for EACH outer iteration
            print(a, b)
    # n × n = O(n²)

If the inner loop's range depends on the outer index (as in the duplicate-pair check from Chapter 2), the total work is still O(n²) — the exact count is smaller (n(n-1)/2 comparisons instead of n²), but Big O drops the constant, and the shape of growth is still quadratic.

5. Loops That Don't Depend on Each Other

Two separate, non-nested loops over the same input add, they don't multiply:

def two_passes(items):
    for item in items:       # O(n)
        print(item)
    for item in items:       # O(n)
        print(item * 2)
    # O(n) + O(n) = O(2n) → simplifies to O(n)

This is a common point of confusion — it's easy to see two loops and assume O(n²). The test is whether one loop is inside the other (multiply) or after it (add).

6. Dropping Constants and Lower-Order Terms

Big O describes growth trends, so constants and smaller terms are dropped once you've identified the dominant term:

O(2n)         → O(n)
O(n + 100)    → O(n)
O(n² + n)     → O(n²)      — n² dominates n as n grows large
O(3n² + 2n + 5) → O(n²)

Rule of thumb: keep the fastest-growing term, drop everything else — including any multiplying or additive constants attached to it.

7. Function Calls Inside Loops

When a loop calls a function, multiply the loop's iteration count by that function's own complexity:

def contains(items, target):     # O(n) — from Chapter 2
    for item in items:
        if item == target:
            return True
    return False
 
def check_all(list_of_lists, target):
    for items in list_of_lists:        # say this runs m times
        if contains(items, target):    # O(n) each call
            print("found")
    # m × O(n) = O(m × n)

This is a common trap in interviews — calling .count(), in on a list, or another helper function inside a loop silently adds a multiplicative factor that's easy to miss if you only look at the loop itself.

8. Summary & Next Steps

Key Takeaways

Sequential code adds complexities; nested code multiplies them.
Two independent loops over the same input are O(n), not O(n²) — only nested loops multiply.
Always check whether a loop calls a function with its own non-constant complexity (like in on a list, or .count()) — that multiplies into the total.
Simplify by keeping only the fastest-growing term and dropping constants.

Concept Check

Why do two sequential O(n) loops simplify to O(n), while two nested O(n) loops become O(n²)?
What's the time complexity of a loop that runs n times, calling a function that does an O(n) linear search each time?
Why does Big O drop constants like the 2 in O(2n)?

Next Chapter

→ Chapter 4: Space Complexity Analysis

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