Big-O: Measuring the Cost · Data Structures & Algorithms

Ch 1 · Thinking Like a Computer Scientist — card 2 of 3.

When we ask "is this fast?", we do not mean seconds on your laptop — we mean: as the input grows, how fast does the work grow? That is Big-O notation.

Read it as "the number of steps, roughly, for n items":

• ✅ O(1) — constant. Same work no matter the size. (Grabbing item #5 from a list.)
• ✅ O(log n) — logarithmic. Doubling the data adds just one step. (Binary search.)
• ⚠️ O(n) — linear. Twice the data, twice the work. (Scanning every item once.)
• ⚠️ O(n log n) — the good sorts. (Merge sort, Tim sort.)
• ❌ O(n²) — quadratic. 10× the data, 100× the work. (Comparing every pair.)

# O(1) — one step, no matter how big the list is
def first_item(items):
    return items[0]

# O(n) — touches every item once
def contains(items, target):
    for item in items:        # n steps in the worst case
        if item == target:
            return True
    return False

print(first_item([10, 20, 30]))   # 10
print(contains([10, 20, 30], 20)) # True