Measuring Efficiency: Big-O & Complexity

What you'll learn

"Which is faster?" is the question you'll ask about every structure in this course. The answer is Big-O notation — a way to describe how an algorithm's cost grows as the input grows, without caring about the specific machine, language, or clock speed.

By the end you'll be able to:

• Explain why we measure growth instead of seconds
• Read O, Ω, and Θ notation
• Recognize the common complexity classes on sight
• Analyze loops and nested loops to find an algorithm's Big-O

Why growth, not seconds

Wall-clock time is a bad measuring stick: it depends on the computer, the language, other running programs, and luck. Instead we count the number of basic operations as a function of the input size n, and ask how that count grows as n gets large. A phone and a supercomputer disagree on seconds, but they agree that a O(n²) algorithm scales far worse than a O(n) one.

Big-O, Ω and Θ

Three related bounds describe an algorithm's growth:

In everyday use, "Big-O" usually means the worst-case upper bound, because that's the guarantee you can rely on.

The complexity classes

Drag the slider to change n. Notice how O(1) and O(log n) barely move, O(n) rises steadily, and O(2ⁿ) and O(n!) explode off the chart almost immediately — look at the operation counts in the table.

Best, worst & average case

The same algorithm can behave differently depending on the input. Searching a list for a value is O(1) if it's the very first element (best case) but O(n) if it's last or missing (worst case). We usually design and compare using the worst case, occasionally the average when the worst case is rare (hash tables are the classic example).

Analyzing code

You can read Big-O straight from the structure of the code. A single pass over the data is O(n); an independent constant amount of work is O(1):

# O(1): one operation, whatever the size
first = items[0]

# O(n): work grows with the size
total = 0
for x in items:
    total += x

A loop nested inside another loop multiplies their counts — roughly n × n, which is O(n²):

# O(n²): a loop inside a loop
for i in range(len(items)):
    for j in range(i + 1, len(items)):
        if items[i] == items[j]:
            print("duplicate:", items[i])

And whenever each step halves the remaining work, the count is O(log n) — because you can only halve n about log₂(n) times before reaching 1. This is the secret behind binary search and balanced trees:

# O(log n): the work halves each step
n = len(items)
steps = 0
while n > 1:
    n = n // 2
    steps += 1

Recap & quick check

Now you can measure cost. Next we meet the technique — and the hidden cost — behind trees, graphs, and divide-and-conquer. Next up: Module 3 — Recursion & the Call Stack.