An algorithm is a finite, unambiguous procedure that solves a class of problems. Two algorithms may both be correct yet differ enormously in cost. Big-O notation describes how an algorithm's running time (or memory) grows as the input size n grows, ignoring constant factors and lower-order terms — it captures the shape of growth, not the stopwatch value.

Formally, f(n) = O(g(n)) means there exist constants c and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀. The common growth classes, from best to worst:

Why ignore constants? Because for large n, growth rate dominates everything. An O(n²) algorithm that is heavily optimised will still lose to a sloppy O(n log n) one once n is big enough — and in the real world, n is always getting bigger. Big-O lets you predict scalability without benchmarking every machine.

The star example is binary search. To find a name in a sorted phone book of a million entries, linear search may take a million comparisons; binary search — repeatedly halving the range — takes at most twenty (since 2²⁰ > 10⁶). That is the practical power of O(log n): doubling the data adds just one more step.

We contrast linear and binary search, then implement merge sort — an O(n log n) divide-and-conquer sort — and count operations to feel the difference.

def linear_search(arr, target):       # O(n)
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

def binary_search(sorted_arr, target):    # O(log n) -- requires sorted input
    lo, hi = 0, len(sorted_arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2              # look at the middle
        if sorted_arr[mid] == target:
            return mid
        elif sorted_arr[mid] < target:
            lo = mid + 1                 # discard the lower half
        else:
            hi = mid - 1                 # discard the upper half
    return -1

def merge_sort(a):                        # O(n log n)
    if len(a) <= 1:
        return a                          # base case: already sorted
    mid = len(a) // 2
    left  = merge_sort(a[:mid])           # sort each half (divide)
    right = merge_sort(a[mid:])
    # merge two sorted halves in linear time (conquer):
    result, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:]); result.extend(right[j:])
    return result

data = [9, 3, 7, 1, 8, 2, 6, 5, 4]
ordered = merge_sort(data)
print(ordered)                            # [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(binary_search(ordered, 7))          # 6  (found in ~log2(9) ≈ 4 steps)

Merge sort splits the list in half (log n levels of splitting) and merges each level in O(n) work — multiplying to O(n log n). It beats bubble sort's O(n²) by a factor of n/log n, which for a million items is about 50,000×.