Big-O & Recurrences: growth rates, the Master Theorem, and three warm-ups

Growth of functions

For a cost function f(n):

Interviews say “O” when they mean “Θ”: “binary search is O(log n)” means its worst case grows like log n.

Rules that do most of the work:

• Drop constants and lower-order terms: 3n² + 10n + 7 = Θ(n²).
• The log base doesn’t matter: log₂ n and log₁₀ n differ by a constant factor.
• Sequential steps add, nested steps multiply: a loop of n containing a log n search is Θ(n log n).
• Count what dominates: for recursion, count calls times work per call (or use a recurrence, below).

A useful rule of thumb: about 10⁸ simple operations per second in C++ and roughly 10⁷ in Python, so read complexity off the constraints. With n up to 10⁵, an O(n²) solution won’t pass but O(n log n) will.

Recurrences and the Master Theorem

A divide-and-conquer algorithm that splits a problem of size n into a subproblems of size n/b, plus f(n) work to split and combine, costs:

T(n) = a · T(n / b) + f(n)

The recursion tree has log_b n levels; level i has aⁱ nodes. Compare the combine work f(n) with n^(log_b a), the number of leaves:

It doesn’t cover everything. Subtract-and-conquer recurrences like T(n) = T(n − 1) + O(n) (selection sort, naive recursion that peels one element) unroll to n + (n − 1) + … = Θ(n²), and uneven splits need the recursion tree or the Akra–Bazzi method.

50. Pow(x, n)

LeetCode 50. Compute xⁿ for a float x and an integer n that can be negative and as large as 2³¹ in magnitude.

def my_pow_brute(x, n):
    result = 1.0
    for _ in range(abs(n)):
        result *= x
    return result if n >= 0 else 1 / result

def my_pow_recursive(x, n):
    if n < 0:
        return 1 / my_pow_recursive(x, -n)
    if n == 0:
        return 1.0
    half = my_pow_recursive(x, n // 2)  # T(n) = T(n/2) + O(1)
    return half * half * (x if n % 2 else 1)

def my_pow(x, n):
    if n < 0:
        x, n = 1 / x, -n
    result = 1.0
    while n:
        if n & 1:  # this bit of n is set: include the current power of x
            result *= x
        x *= x  # x, x², x⁴, x⁸, ...
        n >>= 1
    return result

Key insight: x¹³ = x⁸ · x⁴ · x¹ because 13 is 1101 in binary. Squaring produces each power of two in one multiplication, so only log₂ n steps are needed. With n up to 2³¹, the brute force would take two billion multiplications.

69. Sqrt(x)

LeetCode 69. Return ⌊√x⌋ for a non-negative integer x, without using a built-in power or square-root function.

def my_sqrt_brute(x):
    r = 0
    while (r + 1) * (r + 1) <= x:
        r += 1
    return r

def my_sqrt(x):
    lo, hi = 0, x
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            lo = mid + 1  # mid works; look for something bigger
        else:
            hi = mid - 1  # mid is too big
    return hi  # the largest value whose square is <= x

def my_sqrt_newton(x):
    r = x
    while r * r > x:
        r = (r + x // r) // 2  # average r and x/r; converges from above
    return r

Key insight: “the largest r with r² ≤ x” is a monotone yes/no question over a sorted range, which is exactly what binary search answers. Binary search on the answer (not on an array) shows up again in capacity, rate, and “minimum maximum” problems.

Merge sort and its recurrence

Self-assigned: implement merge sort and derive its running time.

def insertion_sort(a):
    a = list(a)
    for i in range(1, len(a)):
        x, j = a[i], i - 1
        while j >= 0 and a[j] > x:  # shift bigger elements right
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = x
    return a

def merge_sort(a):
    if len(a) <= 1:
        return list(a)
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])  # 2 · T(n/2)
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):  # O(n) merge
        if left[i] <= right[j]:  # <= keeps equal elements in order (stable)
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    return merged + left[i:] + right[j:]

The recurrence is T(n) = 2T(n/2) + Θ(n): Master Theorem case 2, so Θ(n log n). The recursion tree shows why: every level does n total work in its merges, and halving gives log₂ n levels.

flowchart TD
A[n] --> B[n/2]
A --> C[n/2]
B --> D[n/4]
B --> E[n/4]
C --> F[n/4]
C --> G[n/4]
D --> H[...]
G --> I[...]

Key insight: insertion sort is O(n) on nearly sorted input and has tiny constants, which is why real sorts (Python’s Timsort) use it for short runs and merge the runs merge-sort style. No comparison sort can beat Ω(n log n) in the worst case: there are n! possible orders and each comparison at best halves them, so you need log₂(n!) = Θ(n log n) comparisons.

Patterns to remember

• Halving the problem each step gives log n; halving it but touching everything at each level gives n log n.
• Write the recurrence first, then match it to a Master Theorem case.
• Binary search works on any monotone yes/no question, not only on sorted arrays.