Big-O

Big-O notation describes how an algorithm's work grows as input size grows — not the exact number of operations (that depends on hardware, language, implementation details), but the SHAPE of the growth curve. You've been using these algorithms since Data Structures and Algorithms; this course is about the notation for talking precisely about them.

Instead of timing code (which depends on your specific machine), exercises in this course count OPERATIONS directly — a more precise, fully reproducible way to see the same growth pattern:

def linear_search_count(nums, target):
    count = 0
    for x in nums:
        count += 1
        if x == target:
            return count
    return count

print(linear_search_count(list(range(1000)), 999))  # 1000 -- has to check nearly everything
print(linear_search_count(list(range(1000)), 0))     # 1 -- lucky, found immediately

Compare that to binary search on the SAME growing input:

def binary_search_count(nums, target):
    lo, hi = 0, len(nums) - 1
    count = 0
    while lo <= hi:
        count += 1
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return count
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return count

Run this on lists of size 1,000 vs 1,000,000 (1000x larger) and the comparison count barely changes — roughly 10 vs roughly 20. That's O(log n): doubling the input only adds ONE more comparison, because each comparison eliminates HALF the remaining search space. This is the concrete, countable difference between "linear" and "logarithmic" that Big-O notation is describing.