Lesson 1/25 Ā· šŸ“Š Complexity & Thinking
šŸ“Š Complexity & ThinkingLesson 1/25
Phase 0 Ā· Complexity & Thinking20 min

Big O Notation

The universal language for talking about algorithm efficiency

When you write code, there are always multiple ways to solve the same problem. Big O notation is how we measure which solution is *better*, not by timing it with a stopwatch, but by understanding how it scales.
The question Big O answers: "As the input gets huge, how does the work grow?"
The "Big" in Big O refers to the *dominant* term. We ignore constants and small terms because at scale, only the fastest-growing part matters. O(2n) ā†’ O(n). O(nĀ² + n) ā†’ O(nĀ²).
The Common Complexities (fastest ā†’ slowest):
| Notation | Name | Example ||----------|------|---------|| O(1) | Constant | Array index lookup || O(log n) | Logarithmic | Binary search || O(n) | Linear | Loop through array || O(n log n) | Log-linear | Merge sort || O(nĀ²) | Quadratic | Nested loops || O(2āæ) | Exponential | Recursive Fibonacci |
The difference is dramatic: with n=1,000,000 operations, O(log n) needs ~20 steps. O(nĀ²) needs 1 trillion.
Spot the complexitypython
# O(1), constant, doesn't matter how big the list is
def get_first(items):
    return items[0]

# O(n), linear, one pass through the data
def find_max(items):
    max_val = items[0]
    for item in items:  # n iterations
        if item > max_val:
            max_val = item
    return max_val

# O(nĀ²), quadratic, nested loops
def has_duplicate(items):
    for i in range(len(items)):       # n iterations
        for j in range(len(items)):   # n iterations each
            if i != j and items[i] == items[j]:
                return True
    return False

Nested loops almost always signal O(nĀ²)

šŸ¤”Quick Check

You have a sorted array of 1,000,000 elements. Binary search finds an element in ~20 steps. What is its Big O?

šŸ¤”Quick Check

Which code is O(nĀ²)?

Practice Exercises

0/2 solved
Exercise 1 of 2easy
ā± 00:00

Classify the Complexity

Analyze each function and print its Big O complexity.
Expected output:find_item: O(n)sum_pairs: O(n^2)binary_lookup: O(log n)
solution.py
1 / 2
Exercise 2 of 2medium
ā± 00:00

Improve the Algorithm

This O(nĀ²) duplicate checker is slow. Rewrite has_duplicate_fast to run in O(n) using a set.
Expected output: True
solution.py
2 / 2
Solve all 2 exercises to unlock completion
Next