Divide & conquer + Master theorem

pythonimport math

def master_case(a, b, f_exp):
    """a, b as in T(n)=a T(n/b)+f(n); f_exp = exponent p in f(n)=Theta(n^p)."""
    watershed = math.log(a, b)              # log_b(a)
    if abs(f_exp - watershed) < 1e-9:
        return f"Case 2: T(n) = Theta(n^{watershed:.3f} * log n)"
    if f_exp < watershed:
        return f"Case 1: T(n) = Theta(n^{watershed:.3f})"
    return f"Case 3: T(n) = Theta(n^{f_exp:.3f})"

print("merge sort   ", master_case(2, 2, 1))    # a=2,b=2,f=n^1
print("binary search", master_case(1, 2, 0))    # a=1,b=2,f=n^0
print("naive matmul ", master_case(8, 2, 2))    # a=8,b=2,f=n^2
print("Strassen     ", master_case(7, 2, 2))    # a=7,b=2,f=n^2
print("Karatsuba    ", master_case(3, 2, 1))    # a=3,b=2,f=n^1

pythondef merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):     # each comparison consumes one element
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:]); out.extend(right[j:])
    return out

def merge_sort(a):
    if len(a) <= 1:                             # base case: T(1)=O(1)
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])                  # a=2 subproblems
    right = merge_sort(a[mid:])                 # ...each of size n/2
    return merge(left, right)                   # combine in Theta(n)

data = [5, 2, 9, 1, 7, 3, 8, 4, 6, 0]
print(merge_sort(data))
print("stable + correct:", merge_sort(data) == sorted(data))

pythonimport random

def quickselect(a, k):
    """Return the k-th smallest (0-indexed) element of list a."""
    if len(a) == 1:
        return a[0]
    pivot = random.choice(a)
    lo = [x for x in a if x < pivot]
    eq = [x for x in a if x == pivot]
    hi = [x for x in a if x > pivot]
    if k < len(lo):
        return quickselect(lo, k)               # recurse ONE side only
    if k < len(lo) + len(eq):
        return pivot                            # k lands in the pivot block
    return quickselect(hi, k - len(lo) - len(eq))

random.seed(7)
data = [5, 2, 9, 1, 7, 3, 8, 4, 6, 0]
got = [quickselect(data[:], k) for k in range(len(data))]
print("selected in rank order:", got)
print("matches sorted:", got == sorted(data))

pythondef lower_bound(a, target):
    lo, hi = 0, len(a)                          # half-open interval [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1                        # mid too small -> discard left half
        else:
            hi = mid                            # keep mid as a candidate
    return lo

def upper_bound(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

a = [1, 2, 2, 2, 4, 6, 6, 9]
lb, ub = lower_bound(a, 2), upper_bound(a, 2)
print("first >= 2 at index", lb, "; first > 2 at index", ub)
print("count of 2s:", ub - lb)
print("insertion point for 5:", lower_bound(a, 5))

pythondef karatsuba(x, y):
    if x < 10 or y < 10:                         # base case: single digit
        return x * y
    n = max(len(str(x)), len(str(y)))
    half = n // 2
    high_x, low_x = divmod(x, 10 ** half)
    high_y, low_y = divmod(y, 10 ** half)
    z0 = karatsuba(low_x, low_y)                 # bd
    z2 = karatsuba(high_x, high_y)               # ac
    z1 = karatsuba(low_x + high_x, low_y + high_y) - z2 - z0   # ad+bc via ONE mult
    return z2 * 10 ** (2 * half) + z1 * 10 ** half + z0

import random
random.seed(1)
ok = all(karatsuba(a, b) == a * b
         for a, b in ((random.randint(0, 10**12), random.randint(0, 10**12))
                      for _ in range(1000)))
print("1000 random products all correct:", ok)
print("example:", karatsuba(1234567, 89012345), "==", 1234567 * 89012345)