DSData Structures & Algorithms · Lesson 1 of 9

Big-O: Measuring Speed

Before learning any data structure, you need the vocabulary for comparing them. Big-O notation describes how an algorithm's work grows as its input grows — the single most useful idea in this track.

Timing code in seconds is fragile: a faster laptop changes the number, a bigger input changes it more. Big-O ignores the machine and asks one question — when the input gets 10× bigger, how much more work happens? If the work also grows 10×, that's O(n), linear. If it grows 100×, that's O(n²), quadratic. If it barely grows at all, that's O(log n) or O(1). The letter n is the input size: items in a list, characters in a string, users in a database.

Python


# O(1) — constant: same work no matter how big the list
def first_item(items):
    return items[0]

# O(n) — linear: touches every item once
def total(items):
    result = 0
    for x in items:          # n iterations
        result += x
    return result

# O(n²) — quadratic: for every item, loop over every item
def has_duplicate_slow(items):
    for i in range(len(items)):
        for j in range(len(items)):     # n * n comparisons
            if i != j and items[i] == items[j]:
                return True
    return False

# O(n) — same job, one pass with a set (next lessons explain why)
def has_duplicate_fast(items):
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

The common classes, fastest to slowest: O(1) constant, O(log n) logarithmic (halve the problem each step — binary search), O(n) linear, O(n log n) the best sorting can do in general, O(n²) quadratic (nested loops over the same data), O(2ⁿ) exponential (try every combination — hopeless past ~30 items). Big-O drops constants and small terms: O(2n + 5) is just O(n), because for large n the multiplier stops mattering compared to the growth shape.

Text


n = 1,000 items, 1 operation = 1 microsecond:

O(1)        1 op            instant
O(log n)    ~10 ops         instant
O(n)        1,000 ops       1 ms
O(n log n)  ~10,000 ops     10 ms
O(n^2)      1,000,000 ops   1 second
O(2^n)      way too many    heat death of universe

Same table at n = 1,000,000:
O(n)        1 second
O(n^2)      11.5 DAYS       <- why nested loops kill big data

✦ Tip
Practical habit: whenever you write a loop inside a loop over the same data, pause and ask if a set or dictionary could remove the inner loop. That one reflex converts more O(n²) code to O(n) than any other trick.