gistfile1.py

def find_elements(K, N):
    t = len(K)
    n = len(N)
    if empty: return, the base case

    # Split K into two pieces:
    left_K = K[ 0:int(t/2) ]   # O(1)
    right_K = K[ int(t/2):t ]  # O(1)

    # Split N into two pieces:
    middle_N = find_median(N) # Assumption: This takes O(n) time.
                              # I don't care about the details
    left_N = [ x for x in N if x < middle_N] # O(n)
    right_N = [ x for x in N if x > middle_N] # O(n)

    return (find_elements(left_K, left_N)
            +
            find_elements(right_K, right_N))

    # At level i (and there are log(t) such levels), we have
    # partitioned the input into 2^i potentially uneven parts.

    # Call these parts w_1, w_2, ..., w_{2^i}.
    # These are fractions: w_1 + w_2 + ... = 1
    # so similarly, w_1*n + w_2*n + w_3*n + ... = n

    # The total work done at level i is:
    # sum over all parts of {c_j * w_j * n}
    # = sum from j=1 to (2^i) of {c_j * w_j * n}
    # = (c_1*w_1*n) + (c_2*w_2*n) + (c_3*w_3*n) + ...
    # = C·W·n    (vector dot product)
    # = C n

    # Since there are log(t) such levels, this takes O( C log(t) n )