Computer Science Roadmap

Learn computing fundamentals, programming, algorithms, systems, and software engineering.

Overall Progress0%

Complexity & Big O

Explanation

Big O notation describes how the time or memory an algorithm uses grows as the size of its input grows. It deliberately ignores constants and small terms, because at large scale the dominant term is what matters: an algorithm that takes 3n + 50 steps is still described as O(n), because doubling the input roughly doubles the work. The most important growth rates to recognize are: O(1) constant time, where the work does not depend on input size; O(log n), where each step cuts the problem in half, like binary search; O(n) linear, where the work grows in proportion to the input; O(n log n), typical of efficient sorting; and O(n^2) quadratic, where nested loops over the input multiply the work. Space complexity asks the same question about memory. A function that creates a copy of the input uses O(n) extra space, while one that only keeps a few counters uses O(1). The practical skill is not memorizing definitions but reading code and predicting its growth. A single loop is usually O(n); two nested loops are usually O(n^2); a loop that repeatedly halves a range is O(log n). Recognizing these patterns lets you choose the right approach before your code slows to a crawl on large inputs.

Why Efficiency Matters

The same task can be solved by algorithms that behave very differently as the input grows. A function that runs in a second for 1,000 items might take hours for a million if its growth is poor. Complexity analysis predicts this before you ever run the code.

Choosing a good algorithm matters more than a faster machine.
Big O measures growth, not exact runtime.

Common Growth Rates

Notation	Name	What it means
O(1)	Constant	Same work regardless of input size
O(log n)	Logarithmic	Halves the problem each step
O(n)	Linear	Grows in proportion to input size
O(n log n)	Linearithmic	Efficient sorting
O(n²)	Quadratic	Nested loops over the input

How to Read Complexity

Find the loops — a single loop is usually O(n).
Nested loops multiply: two nested loops are O(n²).
Halving the range each step is O(log n).
Drop constants and keep only the dominant term.

Syntax

Reading common complexitiespython

1def constant_time(items):      # O(1)2    return items[0]3 4def linear_scan(items):        # O(n)5    total = 06    for item in items:7        total += item8    return total9 10def all_pairs(items):          # O(n^2)11    for a in items:12        for b in items:13            print(a, b)14 15def binary_search(items, target):  # O(log n)16    lo, hi = 0, len(items) - 117    while lo <= hi:18        mid = (lo + hi) // 219        if items[mid] == target:20            return mid21        if items[mid] < target:22            lo = mid + 123        else:24            hi = mid - 125    return -1

Look at the loop structure, not the names of the functions: one loop is linear, nested loops are quadratic, and halving the range is logarithmic.

Examples

Nested loops are quadratic

Two loops over the same input produce every pair, which is n * n = O(n^2) work.

python

1items = [1, 2, 3]2count = 03for a in items:4    for b in items:5        count += 16print(count)

Output

Halving the range is logarithmic

Binary search discards half the remaining elements each step, so it needs only about log2(n) steps.

python

1def binary_search(items, target):2    lo, hi = 0, len(items) - 13    while lo <= hi:4        mid = (lo + hi) // 25        if items[mid] == target:6            return mid7        if items[mid] < target:8            lo = mid + 19        else:10            hi = mid - 111    return -112 13print(binary_search([1, 3, 5, 7, 9], 7))

Output

Same result, different cost

Finding duplicates with nested loops is O(n^2); using a set is O(n). Both are correct, but only one scales.

python

1def has_duplicate_slow(items):2    for i in range(len(items)):3        for j in range(i + 1, len(items)):4            if items[i] == items[j]:5                return True6    return False7 8def has_duplicate_fast(items):9    return len(items) != len(set(items))10 11data = [1, 2, 3, 2]12print(has_duplicate_slow(data))13print(has_duplicate_fast(data))

Output

True
True

Key Takeaways

Big O describes how time or space grows with input size.
O(1), O(log n), O(n), O(n log n), and O(n^2) are the core rates.
A single loop is usually O(n); nested loops are usually O(n^2).
Halving the range each step is O(log n).
The dominant term wins; constants are ignored.

← PreviousTrees & Graphs Next →Sorting & Searching