CLRS Chapter 4. Divide and Conquer

chapter 3table of contentschapter 5

source code directory

4.1. The maximum-subarray problem

Implementation

A divide-and-conquer implementation of the maximal subarray finder is as follows:

from math import floor


infty = float("inf")  # -infty is used as the universal lower bound

def maximal_subarray(A, lo, hi):
    if lo == hi:
        return (A[lo], lo, hi)
    else:
        mid = lo + floor((hi - lo)/2)
        # the divide-and-conquer step
        (lsum, llo, lhi) = maximal_subarray(A, lo, mid)
        (rsum, rlo, rhi) = maximal_subarray(A, mid+1, hi)
        (csum, clo, chi) = maximal_crossing_subarray(A, lo, mid, hi)
        # pick the maximal result
        if (lsum >= csum) and (lsum >= rsum):
            return (lsum, llo, lhi)
        elif (rsum >= lsum) and (rsum >= csum):
            return (rsum, rlo, rhi)
        else:
            return (csum, clo, chi)

def maximal_crossing_subarray(A, lo, mid, hi):
    """search left of mid and right of mid separately, then add"""
    (lsum, llo) = maximal_subarray_fixed_starting_point(A, mid, lo, -1)
    (rsum, rhi) = maximal_subarray_fixed_starting_point(A, mid+1, hi, 1)
    return (lsum + rsum, llo, rhi)

def maximal_subarray_fixed_starting_point(A, start, end, direction):
    total, subtotal, max_index = -infty, 0, start
    for i in range(start, end + direction, direction):
        subtotal = subtotal + A[i]
        if subtotal > total:
            total, max_index = subtotal, i
    return (total, max_index)
>>> A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
>>> maximal_subarray(A, 0, len(A)-1)
(43, 7, 10)

Exercises

4.1-1. What does find-maximaum-subarray return when all elements of are negative?

find-maximum-subarray in the text is equivalent to maximal_subarray above, so let us take a look at the latter. We shall show that maximal_subarray(A, 0, len(A)-1) returns the maximum element of whenever consists entirely of negative numbers.

We first observe that maximal_subarray_fixed_starting_point(A, start, end, direction) returns (A[start], start) for all legal inputs of start and end. From this, we see that maximal_crossing_subarray(A, lo, mid, hi) returns (A[mid] + A[mid+1], mid, mid+1). Since consists entirely of negative numbers,

whence it follows that the return value of maximal_subarray cannot come from maximal_crossing_subarray.

The only return values of maximal_subarray that does not come from maximal_crossing_subarray are the terms of . Since the if-elif-else block at the end of maximal_subarray returns the maximum, we conclude that maximal_subarray(A, 0, len(A)-1) returns the maximum element of , as was to be shown.

4.1-2. Write pseudocode for the brute-force method of solving the maximum-subarray problem. Your procedure should run in time.

infty = float("inf") # -infty is used as the universal lower bound

def maximal_subarray_brute_force(A):
    n = len(A)
    max_sum = -infty
    for i in range(n):
        iterative_sum = 0
        for j in range(i, n):
            iterative_sum += A[j]
            if iterative_sum > max_sum:
                max_sum = iterative_sum
                max_lo, max_hi = i, j
    return (max_sum, max_lo, max_hi)
>>> A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
>>> maximal_subarray_brute_force(A)
(43, 7, 10)
>>> A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
>>> maximal_subarray(A, 0, len(A)-1)
(43, 7, 10)

It is not hard to see that maximal_subarray_brute_force is correct, as it compares every possible sub-sum.

Assuming that the if clause is never satisfied, we can compute the lower bound of the running time as follows:

The if clause only adds constant time to the computation, and so the upper bound of the running time is . It follows that maximal_subarray_brute_force runs in time.

4.1-3. Implement both the brute-force and recursive algorithms for the maximum-subarray problem on your own computer. What problem size gives the crossover point at which the recursive algorithm beats the brute-force algorithm? Then, change the base case of the recursive algorithm to use the brute-force algorithm whenever the problem size is less than . Does that change the crossover point?

>>> import random

50 elements:

>>> L1 = random.sample(range(-1000, 1000), 50)
>>> L2 = random.sample(range(-1000, 1000), 50)
>>> L3 = random.sample(range(-1000, 1000), 50)
>>> %%timeit
... maximal_subarray(L1, 0, len(L1)-1)
... maximal_subarray(L2, 0, len(L2)-1)
... maximal_subarray(L3, 0, len(L3)-1)
231 µs ± 1.94 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %%timeit
... maximal_subarray_brute_force(L1)
... maximal_subarray_brute_force(L2)
... maximal_subarray_brute_force(L3)
227 µs ± 978 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each)

60 elements:

>>> L1 = random.sample(range(-1000, 1000),60)
>>> L2 = random.sample(range(-1000, 1000),60)
>>> L3 = random.sample(range(-1000, 1000),60)
>>> %%timeit
... maximal_subarray(L1, 0, len(L1)-1)
... maximal_subarray(L2, 0, len(L2)-1)
... maximal_subarray(L3, 0, len(L3)-1)
285 µs ± 6.63 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %%timeit
... maximal_subarray_brute_force(L1)
... maximal_subarray_brute_force(L2)
... maximal_subarray_brute_force(L3)
312 µs ± 1.21 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

It follows that for this particular example. Let us now modify the recursive algorithm to include the brute-force algorithm for all lists of size at most, say, 55:

def maximal_subarray_mixed(A, lo, hi):
    if hi - lo <= 55:
        (brute_sum, brute_lo, brute_hi) = maximal_subarray_brute_force(
            A[lo:hi+1])
        return (brute_sum, brute_lo + lo, brute_hi + hi)
    else:
        mid = lo + floor((hi-lo)/2)
        (lsum, llo, lhi) = maximal_subarray(A, lo, mid)
        (rsum, rlo, rhi) = maximal_subarray(A, mid+1, hi)
        (csum, clo, chi) = maximal_crossing_subarray(A, lo, mid, hi)
        if (lsum >= csum) and (lsum >= rsum):
            return (lsum, llo, lhi)
        elif (rsum >= lsum) and (rsum >= csum):
            return (rsum, rlo, rhi)
        else:
            return (csum, clo, chi)

Let us test the new algorithm.

60 elements:

>>> L1 = random.sample(range(-1000, 1000),60)
>>> L2 = random.sample(range(-1000, 1000),60)
>>> L3 = random.sample(range(-1000, 1000),60)
>>> %%timeit
... maximal_subarray(L1, 0, len(L1)-1)
... maximal_subarray(L2, 0, len(L2)-1)
... maximal_subarray(L3, 0, len(L3)-1)
279 µs ± 3.09 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %%timeit
... maximal_subarray_mixed(L1, 0, len(L1)-1)
... maximal_subarray_mixed(L2, 0, len(L2)-1)
... maximal_subarray_mixed(L3, 0, len(L3)-1)
278 µs ± 989 ns per loop (mean ± std. dev. of 7 runs, 1000 loops each)

70 elements:

>>> L1 = random.sample(range(-1000, 1000),70)
>>> L2 = random.sample(range(-1000, 1000),70)
>>> L3 = random.sample(range(-1000, 1000),70)
>>> %%timeit
... maximal_subarray(L1, 0, len(L1)-1)
... maximal_subarray(L2, 0, len(L2)-1)
... maximal_subarray(L3, 0, len(L3)-1)
330 µs ± 1.61 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %%timeit
... maximal_subarray_mixed(L1, 0, len(L1)-1)
... maximal_subarray_mixed(L2, 0, len(L2)-1)
... maximal_subarray_mixed(L3, 0, len(L3)-1)
330 µs ± 2.47 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

We see that the crossover point increases by 10 or so, but this is hardly an improvement.

4.1-4. Suppose we change the definition of the maximum-subarray problem to allow the result to be an empty subarray, where the sum of the values of an empty subarray is 0. How would you change any of the algorithms that do not allow empty subarrays to permit an empty subarray to be the result?

Only the main routine needs to be changed:

from math import floor

def maximal_subarray_allow_empty_subarray(A, lo, hi):
    if lo == hi:
        if A[lo] < 0:
            return (0, -1, -1)  # allow for empty array, labeled by -1
        else:
            return (A[lo], lo, hi)
    else:
        mid = lo + floor((hi - lo)/2)
        (lsum, llo, lhi) = maximal_subarray(A, lo, mid)
        (rsum, rlo, rhi) = maximal_subarray(A, mid+1, hi)
        (csum, clo, chi) = maximal_crossing_subarray(A, lo, mid, hi)
        if (lsum < 0) and (rsum < 0) and (csum < 0):
            return (0, -1, -1)  # allow for empty array, labeled by -1
        elif (lsum >= csum) and (lsum >= rsum):
            return (lsum, llo, lhi)
        elif (rsum >= lsum) and (rsum >= csum):
            return (rsum, rlo, rhi)
        else:
            return (csum, clo, chi)
>>> A = [-1, -2, -3, -4, -5, -6, -7]
>>> maximal_subarray_allow_empty_subarray(A, 0, len(A)-1)
(0, -1, -1)

4.1-5. Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum subarray of A[1..j], extend the answer to find a maximum subarray ending at index by using the following observation: a maximum subarray of A[1..j+1] is either a maximum subarray of A[1..j] or a subarray A[i..j+1] for some . Determine a maximum subarray of the form A[i..j+1] in constant time based on knowing a maximum subarray ending at index .

We fix an index and suppose that is a maximum subarray of . We pick another index such that

By the maximality of in , every maximum subarray of must either equal to or contain . Now,

whence we conclude that

Using the above observation, we devise a linear-time algorithm for the maximum-subarray problem.

Given an array , we observe that is the (unique) maximum subarray of . We now apply the above observation inductively to produce a maximum subarray of , a process known as Kadane’s algorithm.

def kadane(A):
    lo, hi, total = 0, 0, 0
    tail_lo, tail_hi, tail_total = 0, 0, 0
    for j in range(1, len(A)-1):
        if tail_total + A[j] <= A[j]:
            tail_lo, tail_hi, tail_total = j, j, A[j]
        else:
            tail_lo, tail_hi, tail_total = tail_lo, j, tail_total+A[j]
        
        if tail_total >= total:
            lo, hi, total = tail_lo, tail_hi, tail_total
    return (total, lo, hi)
>>> A = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]
>>> maximal_subarray(A, 0, len(A)-1)  # see the implementation subsection
(43, 7, 10)
>>> kadane(A)
(43, 7,1 0)

4.2 Strassen’s algorithm for matrix multiplication

See my blog post for details.

Exercises

4.2-1. Use Strassen’s algorithm to compute the matrix product

Show your work.

Observe first that

The product is

4.2-2. Write pseudocode for Strassen’s algorithm

The implementation below makes use of NumPy to reduce the implementation overhead on basic matrix operations.


import numpy as np

def strassen(A, B):
    n = len(A)
    if n == 1:
        return A * B

    # block matrices; // is integer division
    a = np.array([[A[:n//2, :n//2], A[:n//2, n//2:]],
                   A[n//2:, :n//2], A[n//2:, n//2:]]])
    b = np.array([[B[:n//2, :n//2], B[:n//2, n//2:]],
                   B[n//2:, :n//2], B[n//2:, n//2:]])

    s1 = b[0,1] - b[1,1]
    s2 = a[0,0] + a[0,1]
    s3 = a[1,0] + a[1,1]
    s4 = b[1,0] - b[0,0]
    s5 = a[0,0] + a[1,1]
    s6 = b[0,0] + b[1,1]
    s7 = a[0,1] - a[1,1]
    s8 = b[1,0] + b[1,1]
    s9 = a[0,0] - a[1,0]
    s10 = b[0,0] + b[0,1]

    p1 = strassen(a[0,0], s1)
    p2 = strassen(s2, b[1,1])
    p3 = strassen(s3, b[0,0])
    p4 = strassen(a[1,1], s4)
    p5 = strassen(s5, s6)
    p6 = strassen(s7, s8)
    p7 = strassen(s9, s10)

    c = np.zeros((n, n))  # initialize an n-by-n matrix
    c[:n//2, :n//2] = p5 + p4 - p2 + p6
    c[:n//2, n//2:] = p1 + p2
    c[n//2:, :n//2] = p3 + p4
    c[n//2:, n//2:] = p5 + p1 - p3 - p7

    return c
>>> A = np.array([[1, 3], [7, 5]])
>>> B = np.array([[6, 8], [4, 2]])
>>> np.dot(A, B)  # matrix multiplication
[[18 14]
 [62 66]]
>>> strassen(A, B)
[[18. 14.]
 [62. 66.]]
>>> A = np.array([[5, 2, 6, 1],
...               [0, 6, 2, 0],
...               [3, 8, 1, 4],
...               [1, 8, 5, 6]])
>>> B = np.array([[7, 5, 8, 0],
...               [1, 8, 2, 6],
...               [9, 4, 3, 8],
...               [5, 3, 7, 9]])
>>> np.dot(A, B)  # matrix multiplication
[[ 96  68  69  69]
 [ 24  56  18  52]
 [ 58  95  71  92]
 [ 90 107  81 142]]
>> strassen(A, B)
[[ 96.  68.  69.  69.]
 [ 24.  56.  18.  52.]
 [ 58.  95.  71.  92.]
 [ 90. 107.  81. 142.]]

4.2-3. How would you modify Strassen’s algorithm to multiply matrices in which is not an exact power of 2? Show that the resulting algorithm runs in time .

For each matrix , we let be the unique integer such that and augment with an identity matrix as follows:

We then have

from which we can extract in constant time. It thus suffices to compute the time complexity of the matrix multiplication .

Observe that

by the monotonicity of . Similarly,

Now,

and so

It follows that , whence applying Strassen’s algorithm to the augmented matrices does not incur any additional asymptotic time complexity.

4.2-4. What is the largest such that if you multiply matrices using multiplications (not assuming commutativity of multiplication), then you can multiply matrices in time ? What would be the running time of this algorithm be?

The recurrence relation to solve is

Observe that . By the master theorem (), we have

where is and for some and all sufficiently large .

Since implies that , we see that whenever . On the other hand, if , then then inequality

never holds for any reagrdless of which we choose. It follows that we must have in order to multiply -by- matrices in time , and the running time is

4.2-5. V. Pan has discovered a way of multiplying matrices using 132,464 multiplications, a way of multiplying matrices using 143,630 multiplications, and a way of multiplying matrices using 155,424 multiplications. Which method yields the best asymptotic running time when used in a divide-and-conquer matrix-multiplication algorithm? How does it compare to Strassen’s algorithm?

The recurrence relations to solve are

Observing that , we invoke the master theorem () to conclude that

Since , we conclude that is better than the running time of Strassen.

Observe now that . The master theorem () implies that

Similarly as above, we conclude that is better than the running time of Strassen.

Finally, we observe that , which implies that

by the master theorem (). Similarly as above, we conclude that is better than the running time of Strassen.

We conclude that

where refers to the runing time of Strassen.

4.2-6. How quickly can you multiply a matrix by an matrix, using Strassen’s algorithm as a subroutine? Answer the same question with the order of the input matrices reversed.

Using block matrix multiplication

we can multiply a matrix by an matrix through iterations of Strassen. It follows that the computation takes .

Similarly, we use block matrix multiplication

we can multiply an matrix by a matrix through iterations of STrassen. It follows that the computation takes .

4.2-7. Show how to multiply the complex numbers and using only three multiplcations of real numbers. The algorithm should take , , , and as input and produce the real component and the imaginary component separately.

We set , , and . Observe that

and that

It follows that

which only requires three real multiplications.

This algorithm is commonly known as the Karatsuba algorithm.

The substitution method for solving recurrences

Exercises

4.3-1. Show that the solution of is .

We let be an arbitrary constant, to be chosen later. We fix a postive integer and assume that

for all . We shall show that

Observe that

By choosing , we see that for all , from which it follows that

as was to be shown.

To turn the above argument into a complete induction proof, we observe that

Since , it suffices to find such that

Choosing any , we see that

as was to be shown. The desired result now follows from mathematical induction with base case .

4.3-2. Show that the solution of is .

We first examine the recurrence for .

We let be an arbitrary constant, to be chosen later. We fix a positive integer and assume that

for all . We shall show that

Observe that

We can bound the last expression by if and only if

The above inequality is equivalent to

Recalling that , we note that

Choosing , we see that

It now follows that

as was to be shown.

To turn the above argument into a complete induction proof, we observe that

for all Since , it suffices to find such that

The above inequality is equivalent to

which, in turn, is equivalent to

We pick any that satisfies the last inequality and set , so that

The desired result now follows from mathematical induction with base case .

4.3-3. We saw that the solution of is . Show that the solution of this recurrence is also . Conclude that the solution is .

We first examine the recurrence for .

We let be an arbitrary constant, to be chosen later. We fix a positive integer and assume that

for all . We shall show that

Observe that

The inequality

is equivalent to

which, in turn, is equivalent to

Since , we see that

We claim that the function

is monotonically decreasing on . Indeed, we have that

from which we conclude that . Monotonicity now follows.

The monotonicity of implies that

Setting , we see that holds, whence holds. We conclude that

with this choice of , as was to be shown.

To turn the above argument into a complete induction proof, we observe that yields

as is typically assumed to be nonnegative.

The desired result now follows from mathematical induction with base case .

4.3-4. Show that by making a different inductive hypothesis, we can overcome the difficulty with the boundary condition for recurrence (4.19) without adjusting the boundary conditions for the inductive proof.

Recall (4.19):

We let be an arbitrary constant, to be chosen later. We fix a positive integer and assume that

for all . We shall show that

Observe that

, we have , so that

To turn the above argument into a complete induction proof, we observe that

The desired result now follows from mathematical induction with base case .

4.3-5. Show that is the solution to the “exact” recurrence (4.3) for merge sort.

Recall (4.3):

We let and , to be chosen later. We fix a positive integer and assume that

for all . We shall show that

Since , we have the double-ended estimate

where the constants and are to be chosen later.

We first establish the upper bound. Since ,

, and so . It then follows that

whence any choice of and with yields

Let us now establish the lower bound. Since ,

, and so . It then follows that

whence any choice of and with yields

We have thus shown that

under the assumption that

holds for all .

To turn the above argument into a complete induction proof, we set and and observe that, for ,

and that

It follows from mathematical induction that with base case .

4.3-6. Show that the solution to is .

Assume that , so that .

We let , to be chosen later. We fix a positive integer and assume that

for all . We shall show that

Observe that

Now, , and so

and

It follows that

Since , we have , and so

It thus suffices to pick such that

keeping in mind that . Since and are both positive under this condition, we need only to pick large enough that

Letting , we obtain

under the assumption that

for all .

To turn the above argument into a complete induction proof, we must show that

But, of course,

It now follows from mathematical induction with base case that

as was to be shown.

4.3-7. Using the master method in Section 4.5, you can show that the solution to the recurrence is . Show that a substitution proof with the assumption fails. Then show how to subtract off a lower-order term to make a substitution proof work.

Since

a naïve substitution argument would yield

Since

for all , the substitution argument fails.

If we assume instead that

for all , then

and the usual substitution proof goes through.

4.3-8. Using the master method in Section 4.5, you can show that the solution to the recurrence is . Show that a substitution proof with the assumption fails. Then show how to subtract off a lower-order term to make a substitution proof work.

Since , a naïve substitution argument would yield

which is larger than for all .

If we assume instead that

for all , then

and the usual substitution proof goes through.

4.3-9. Solve the recurrence by makign a change of variables. Your solution should be asymptotically tight. Do not worry about whether values are integral.

Since

we set and solve instead

The master theorem () shows that

We shall show this by substitution.

We let and , to be chosen later. We fix a positive integer and assume that

for all . We shall show that

We first establish the upper bound:

Now, the lower bound:

To turn the above argument into a complete induction proof, we must show that

Setting , we see that

and that

Mathematical induction with base case now shows that

for all . Since the lower bound agreed with the upper bound, we in fact have the identity

Since , we conclude that

4.4. The recursion-tree method for solving recurrences

Exercises

4.4-1. Use a recursion tree to determine a good asymptotic upper bound on the recurrence . Use the substitution method to verify your answer.

Observe that

Let us verify our guess. To this end, we let , to be chosen later. We fix a positive integer and assume that

for all . We shall show that

Indeed,

To complete the induction proof, we must show that

We set and observe that

as was to be shown. It now follows from mathematical induction with base case that .

4.4-2. Use a recursion tree to determine a good asymptotic upper bound on the recurrence . Use the substitution method to verify your answer.

Observe that

Let us verify our guess. To this end, we let , to be chosen later. We fix a positive integer and assume that

for all . We shall show that

Observe that

So long as , we have , and so

To complete the induction proof, we must show that

To this end, we simply select . The desired result now follows from induction.

4.4-3. Use a recursion tree to determine a good asymptotic upper bound on the recurrence . Use the substitution method to verify your answer.

We first observe the the recurrence relation as it is written above is ill-defined. Indeed,

when is a function defined on . To remedy this issue, we shall consider instead

Observe that

Setting , we obtain

We therefore conjecture that

Since the problem only asks us to establish the upper bound, we shall prove that

We let and , to be chosen later. We fix a positive integer and assume that

for all . We shall show that

Observe that

If we choose and so that and , then we have the bound

How do we choose such and ? The first inequality can be written as

It turns out that this is sufficient to achieve the second inequality:

We also note that the constants must be chosen to satisfy the base case

for an appropriate choice of . Since the smallest that satisfies is , the base case should be chosen so that . This only works if . indeed, if , then

On the other hand, if , then

which is positive if .

Summarizing the above argument, we choose and . For the base case , we have

as is generallly assumed to be nonnegative.

We now assume inductively that

holds for all such that . Now, the inductive hypothesis implies that

as was to be shown. We conclude that .

4.4-4. Use a recursion tree to determine a good asymptotic upper bound on the recurrence . Use the substitution method to verify your answer.

Observe that

Let us verify our guess. To this end, we let , to be chosen later. We fix a positive integer and assume that

for all . We then have

By choosing , we have

for . It now follows from mathematical induction that .

4.4-5. Use a recursion tree to determine a good asymptotic upper bound on the recurrence . Use the substitution method to verify your answer.

To make sense of the term, we consider instead

Since , we see that

Therefore,

Applying to the sum indexed by , we obtain

Applying recursively, we obtain

Let us verify our guess. To this end, we let and , to be chosen later. We fix a positive integer and assume that

for all . We shall show that

Observe that

Since

we see that

Since we must have

we see that

is required for all . This holds when :

Finally, we must pick and so that

holds when . This requires

Setting and , we see that

The choice of and also shows that

whenever

for all . It now follows from mathematical induction with base case that .

4.4-6. Argue that the solution to the recurrence , where is a constant, is by appealing to a recursion tree.

Observe that

where is the binomial coefficient with respect to . It follows that .

4.4-7. Draw the recursion tree for , where is a constant, and provide a tight asymptotic bound on its solution. Verify your bound by the substitution method.

Observe that

We thus conjecture that .

We first establish the upper bound. To this end, we let and , to be chosen later. We fix a positive integer and assume that

for all . We shall show that

Observe that

Therefore, must be chosen so that for all . This holds if .

We now set

and

so that

Moreover, if for all , then

It now follows from induction with base case that .

It remains to show that .

We let and , to be chosen later. We fix a positive integer and assume that for all . Observe that

To ensure that the resulting expression is bounded below by , we must at least have . This holds if .

We assume for now that and set and , so that

Moreover,

and so it follows from mathematical induction with base case that .

We have thus shown that .

4.4-8. Use a recursion tree to give an asymptotically tight solution to the recurrence , where and are constants.

Observe that

We thus conjecture that .

Since for , the recurrence relation cannot hold for . We thus assume that the values of for are given.

We first show the upper bound. To this end, we let , to be chosen later. We shall show that

for all . We first assume that , so that holds for .

Observe that

If , then

and so

We thus assume that

We now fix and assume that holds for . We shall show that holds for .

Observe that

If , then

Since , we have the estimate

Now, , and so

It follows that holds for whenever .

Setting

we see that holds for all . It follows that .

We now establish the lower bound. To this end, we let , to be chosen later. We shall show that

for all . We first assume that , so that holds for .

Observe that

If , then

and so

We thus assume that

We now fix and assume that holds for . We shall show that holds for .

Observe that

If , then

Since , we have , and so

It follows that holds for whenever .

Setting

we have for all . It follows that .

We now conclude that , as was to be shown.

4.4-9. Use a recursion tree to give an asymptotically tight solution to the recurrence , where is a constant in the range and is also a constant.

Observe that

We let and set , so that

for all . The recursion-tree computation yields

We therefore conjecture that

We first establish the upper bound. To this end, we let , to be chosen later. We assume that

for all .

Observe that

Since and , we have that and . Therefore, any

would yield

We now set

so that , and that

whenever for all . It now follows from induction that .

We now establish the lower bound. To this end, we let , to be chosen later. We assume that

for all .

Observe that

Since and , we have that and . Therefore, any

would yield

We now set

so that , and that

whenever for all . It now follows from induction that .

We have thus shown that .

4.5. The master method for solving recurrences

The master theorem, as stated in CLRS, Theorem 4.1

Let and be constants, let be a function, and let be defined on the nonnegative integers by the recurrence

where we interpret to mean either or . Then has the following asymptotic bounds:

  1. If for some constant , then .
  2. If , then .
  3. If for some constant , and if for some constant and all sufficiently large , then .

Exercises

4.5-1. Use the master method to give tight asymptotic bounds for the following recurrences.

a. .

b. .

c. .

d. .

a belongs to case 1, and so

b belongs to case 2, and so

c belongs to case 3, as

for all . Therefore,

d belongs to case 3, as

for all . Therefore,

4.5-2. Professor Caesar wishes to develop a matrix-multiplication algorithm that is asymptotically faster than Strassen’s algorithm. His algorithm will use the divide-and-conquer method, dividing each matrix into pieces of size , and the divide and combine steps together will take time. He needs to determine how many subproblems his algorithm has to create in order to beat Strassen’s algorithm. If his algorithm creates subproblems, then the recurrence for the running time becomes . What is the largest integer value of for which Professor Caesar’s algorithm would be asymptotically faster than Strassen’s algorithm?

We recall that Strassen’s time complexity is . In light of this, it suffices to find the maximum integral value of such that

subject to the restriction that is asymptotically smaller than .

Since , the restriction yields the lower bound

Observe that is equivalent to

which, in turn, is equivalent to

Since , we conclude that

It follows that we must have , whence the optimal integral value of is .

4.5-3. Use the master method to show that the solution to the binary-search recurrence is . (See Exercise 2.3-5 for a description of binary search.)

Since and , we have . Therefore, is asymptotically equivalent to , whence the master method implies that

as was to be shown.

4.5-4. Can the master method be applied to the recurrence ? Why or why not? Give an asymptotic upper bound for this recurrence.

The term in makes it impossible to apply the master method here. , so . Nevertheless, for all , and so for all . It follows that none of the three cases of the master method is applicable.

We shall compute the recursion tree of . Observe:

Since

we conjecture that

To show this, we let , to be chosen later. We assume that

for all . (We pick 16, so that .) We shall show that

Observe that

Since , we have

whenever .

We now set

so that, for ,

Moreover, , and so

for all

implies

It now follows from induction that .

4.5-5. Consider the regularity condition for some constant , which is part of case 3 of the master theorem. Give an example of constants and and a function that satisfies all the conditions in case 3 of the master theorem except the regularity condition.

Let’s first rule out a general class of examples. Let , , , and be arbitrary, and let

Since

we see that setting yields

for all . , and so .

This suggests that we need an oscillating term. Let us pick , , and . Observe that

Whenever is odd, and , and so

It follows that, whenever , the inequality

cannot hold for all .

4.6. Proof of the master theorem

Exercises

4.6-1. Give a simple and exact expression for in equation (4.27) for the case in which is a positive integer instead of an arbitrary real number.

We shall prove a more general result: whenever and , we have the identity

Observe that

This implies, in particular, that

The upper bound of implies that

We suppose for a contradiction that

We can find an integer such that

This implies that

so that

The lower bound of implies that

It now follows from that

which is evidently absurd. We conclude that

Let us now recall (4.27):

We shall show that

whenever is an integer. We proceed by mathematical induction. The case is trivially true. If the case holds, then implies that

as was to be shown.

4.6-2. Show that if , where , then the master recurrence has solution . For simplicity, confine your analysis to exact powers of .

We begin with a remark that

not

Fix . Recall from (4.21) that

Since

we see that

It thus suffices to show that

Since ,

and so

follows from if we can prove, in addition, that

To this end, we recall that is restricted to be of the form for some exponent . We shall show that

for all , where is a constant independent of .

We shall prove by induction on .

We tackle the inductive step first, so as to determine an appropriate value of . Let us fix and assume that

for all , where is a constant to be chosen later. We shall show that

To this end, we observe that

By way of the inductive hypothesis , we bound the above quantity below by

To show , it now suffices to establish the estimate

We write

for each and observe that

implies that , and so we need only to show that

The above inequality is equivalent to

as for all sufficiently large . In fact, if , then for all .

It thus suffices to establish

If , then

Since , we see that

for all , establishing for .

It follows that holds for , which establishes the inductive case of .

To complete the proof of by induction, we must establish the base case , i.e.,

Since we have chosen , the base case holds with equality. The induction proof is now complete.

Finally, follows from and , and we have the desired estimate

Our work here is done.

4.6-3. Show that case 3 of the master theorem is overstated, in the sense that the regularity condition for some constant implies that there exists a constant such that .

We recall from Theorem 4.1 that and . We let and observe that the regularity condition can be rewritten as

Applying times, we obtain

Since , we have the estimate

Now, , and so

implies , and so

where . It follows that

Finally, we remark that implies .

Problems

4-1. Recurrence examples

Give asymptotic upper and lower bounds for in each of the following recurrences. Assume that is constant for . Make your bounds as tight as possible, and justify your answers.

a.

b.

c.

d.

e.

f.

g.

a-f can be solved directly by the master theorem (Theorem 4.1), which we restate below for ease of reference:

Theorem 4.1 (Master theorem). Let and be constants, let be a function, and let be defined on the nonnegative integers by the recurrence

where we interpret to mean either or . Then has the following asymptotic bounds:

  1. If for some constant , then .

  2. If , then .

  3. If for some constant , and if for some constant and all sufficiently large , then .

Problem 4-1a

, so that . Since

and

we see that

Problem 4-1b

and , so that . Since

and

we see that

Problem 4-1c

and , so that . Since , we see that

Problem 4-1d

and , so that . Since

and

we see that

Problem 4-1e

and , so that . Since

we see that

Problem 4-1f

and , so that . Since , we see that

Problem 4-1g

We cannot use the master theorem, as

is not of the form

Observe, however, that

Recalling that

we obtain

where .Since , we have

4-2. Parameter-passing costs

Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an -element array is being passed. This assumption is valid in most systems because a pointer to the array is passed, not the array itself. This problem examines the implications of three parameter-passing strategies:

  1. An array is passed by pointer. Time = .

  2. An array is passed by copying. Time = , where is the size of the array.

  3. An array is passed by copying only the subrange that might be accessed by the called procedure. Time = if the subarray is passed.

a. Consider the recursive binary search algorithm for finding a number in a sorted array (see Exercise 2.3-5). Given recurrences for the worst-case running times of binary search when arrays are passed using each of the three methods above, and give good upper bounds on the solutions of the recurrences. Let be the size of the original problem and be the size of a subproblem.

b. Redo part (a) for the Merge-Sort algorithm from Section 2.3.1.

Problem 4-2a

Recall binary_search from Exercise 2.3-5, which we reproduce below:

from math import floor

def binary_search(A, p, q, v):
    if p > q :
        return -1
    if p == q:
        return p if A[p] == v else -1
    
    mid = p + floor((q-p)/2)
    if A[mid] == v:
        return mid
    else:
        if A[mid] > v:
            return binary_search(A, p, mid-1, v)
        else: # A[mid] < v
            return binary_search(A, mid+1, q, v)

Let be the worst-case running time of binary_search on a list of length . Since it takes constant time to execute all but the recursive step of the algorithm, we have

where is the time it takes to pass a length- subarray of an array of length .

If arrays are passed by pointer, then , and so

By the master theorem (see Section 4.5), we have

If arrays are passed by copying, then , and so

By the master theorem, we have

Finally, if arrays are passed by copying the appropriate subranges, then . We thus have , and so

Problem 4-2b

We recall the non-sentinel version of merge sort from Exercise 2.3-2, which we reproduce below:

import math


def merge(A, p, q, r):
    L, R = A[p,q], A[q:r]
    n,m = q-p, r-q

    i, j, k = 0, 0, p

    while i < n and j < m:
        if L[i] < R[j]:
            A[k] = L[i]
            i += 1
        else:
            j += 1
        k += 1


    while i < n or j < m:
        if i < n:
            A[k] = L[i]
        else:
            A[k] = R[j]
        k += 1

def merge_sort(A, p, r):
    if p+1 < r:
        q = p + math.floor((r-p)/2)
        merge_sort(A, p, q)
        merge_sort(A, q, r)
        merge(A, p, q, r)

Note that the time complexity of merge is . Since we divide the input array in half, the time complexity of merge_sort is

where is the time it takes to pass a length- subarray of an array of length .

Since regardless of how we pass in an array, we conclude that

It follows from the master theorem (see Section 4.5) that

4-3. More recurrence examples

Give asymptotic upper and lower bounds for in each of the following recurrences. Assume that is constant for sufficiently small . Make your bounds as tight as possible, and justify your answers.

a. .

b. .

c. .

d. .

e. .

f. .

g. .

h. .

i. .

j. .

See Section 4.5 for the statement of the master theorem.

Problem 4-3a

Recall from Problem 3-2 that

for every . It follows that

for all , whence the master theorem implies that

Problem 4-3b

We fist show that the master theorem cannot be used here. To this end, we shall show that

for any choice of ,

and that

for any choice of .

Since for all , we have that

for all . This implies . follows from .

For , we observe that each constant furnishes an integer such that

for all . It follows that

for all , and follows.

Finally, we recall from Problem 3-2 that

for every . This implies that each choice of and furnishes an integer such that

for all . Therefore, we see that

for all , and follows.

Let us now proceed without the master theorem.

We let and observe that

Since , we see that

Moreover, , and so

We thus have the estimates

In order to estimate the sum, we define and observe that

whenever . Therefore,

for any choice of index , whence it follows that

Since , we see that

We thus end up with the upper bound

for constants , , and . We conclude that

To establish a lower bound, we set once againd and observe that

whenever . Therefore,

for any choice of index , whence it follows that

Since , we see that

We thus end up with the lower bound

for constants and . We conclude that

We have now completed the proof of the estimate

Problem 4-3c

The recurrence relation in question can be written as

Observe that

Moreover,

for all , and . We can therefore use the master theorem to conclude that

Problem 4-3d

We cannot use the master theorem, as the recurrence relation is not of the form . If, however, we drop the term, we can use the master theorem on

to obtain

Since the term shouldn’t affect the asymptotic behavior of , we conjecture that

To prove , we first fix , so that . Assume inductively that

for all , where is a constant to be chosen later. Observe that

If we choose , then we have

for all , and we have the desired bound

To establish the base case , we choose

so that the inductive step continues to holds, while

for . We now conclude by induction that

To prove , it now remains to show that

To this end, we fix , so that and . Assume inductively that

for all , where is a constant to be chosen later. Observe that

Since , we have

Choosing yields

so that

as was to be shown.

To establish the base case , we choose

so that the inductive step continues to hold, while

for . We now conclude by induction that

as was to be shown. This completes the proof that

Problem 4-3e

Generalizing the computation carried out in Problem 4-3b, we show that a recurrence relation of the form

satisfies the asymptotic estimate

We let and observe that

We have shown in Problem 4-3b that

and so we conclude that

Problem 4-3f

The recurrence relation is not in a form that the master theorem can be applied to, so we must produce an asymptotic estimate directly.

Observe that

From this, let us guess that the accumulation of cost is

for some . Since

we conjecture that

To verify this, we fix and assume inductively that

for all , where and are constants to be chosen. Observe that

Analogously,

So long as and , we have

$D \leq \frac{7}{8}(1+D) \leq \frac{7}{8}(1+C) \leq C,$$

which yields

as was to be shown.

To establish the base case , we choose

so that the inductive case continues to hold, while

and

as was to be shown. This completes the proof of

Problem 4-3g

The recurrence relation is not in a form that the master theorem can be applied to, so we must produce an asymptotic estimate directly.

Observe that

Page 1154 of CLRS shows that

and so we conclude that

Problem 4-3h

The recurrence relation is not in a form that the master theorem can be applied to, so we must produce an asymptotic estimate directly.

Observe that

We have proved in Exercise 3.2-3 that , and so we conclude that

Problem 4-3i

The recurrence relation is not in a form that the master theorem can be applied to, so we must produce an asymptotic estimate directly.

Observe that

where is the double factorial function

We let . If is even, then

In this case,

which is .

If is odd, then

In this case,

We have proved in Exercise 3.2-3 that , and so has the asymptotic estimate of .

We conclude that

Problem 4-3j

The recurrence relation is not in a form that the master theorem can be applied to, so we must produce an asymptotic estimate directly.

Let us begin by making the substitution :

Setting , we see that

Observe that

Since

we see that .

The identity now implies that

4-4. Fibonacci numbers

The problem develops properties of the Fibonacci numbers, which are defined by recurrence (3.22). We shall use the technique of generating functions to solve the Fibonacci recurrence. Define the generating function (or formal power series) as

where is the th Fibonacci number.

a. Show that .

b. Show that

where

and

c. Show that

d. Use part (c) to prove that for , rounded to the nearest integer. (Hint: Observe that .)

Problem 4-4a

Observe that

We then have

Since and for all , we conclude that

Problem 4-4b

It follows at once from 4-4a that

By the quadratic formula,

and the second equality follows.

Finally, we observe that

The third equality now follows.

(To deduce the third equality directly from the second equality, we must carry out the partial fraction decomposition of the second expression.)

Problem 4-4c

Page 1147 of CLRS tells us that

Substituting , we get

Similarly,

The desired identity now follows from the third equality in 4-4b.

Problem 4-4d

We have shown in 4-4c that

for all indices . Since , we have

whence it follows that

In other words, is rounded to the nearest integer.

4-5. Chip testing

Professor Diogenes has supposedly identical integrated-circuit chips that in principle are capable of testing each other. The professor’s test jig accommodates two chips at a time. When the jig is loaded, each chip tests the other and reports whether it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the professor cannot trust the answer of a bad chip. Thus, the four possible outcomes of a test are as follows:

Chip says Chip says Conclusion
is good is good both are good, or both are bad
is good is bad at least one is bad
is bad is good at least one is bad
is bad is bad at least one is bad

a. Show that if at least chips are bad, the professor cannot necessarily determine which chips are good using any strategy based on this kind of pairwise test. Assume that the bad chips can conspire to fool the professor.

b. Consider the problem of finding a single good chip from among chips, assuming that more than of the chips are good. Show that pairwise tests are sufficient to reduce the problem to one of nearly half the size.

c. Show that the good chips can be identified with pairwise tests, assuming that more than of the chips are good. Give and solve the recurrence that describes the number of tests.

Notational Remark

Given two chips and , we write to denote what has to say about . The possible outcomes are, of course, good, and bad.

A test consists of inputting two chips and and receiving the output

Problem 4-5a

Assume that at least chips are bad. Let be the set of all good chips, and let be a set of bad chips of size . We let be the remaining chips, if there are any.

Observe that, for each ,

Let us consider the following adversarial strategy: each returns

and each returns

We now partition the collection of chips by declaring two chips and to be in the same category if and only if

The partition process produces three categories: namely, , , and .

A test does not show which category a pair of chips belongs to. It merely shows whether two chips belong to the same category. Since and are of the same size, this information is insufficient to distinguish the two categories from one another. It follows that the chosen adversarial strategy prevents distinguishing good chips from bad chips.

Problem 4-5b

Let us assume that more than of the chips are good.

We assume that is even, and set . If there is an odd number of chips, we discard one at random to make the number of chips even.

We divide the chips into two groups of equal sizes, and , assigning indices arbitrarily.

For each index , we declare the pair to be in the keep pile if and only if

In other words, either and are both good chips or they are both bad chips.

We also define the discard pile to be the collection of all pairs that do not belong to . We denote by and the number of pairs in and , respectively. We note here that

Moreover, each pair in must contain at least one bad chip, and so

We now observe that contains more than good pairs. Indeed, if contained at most good pairs, then

which is absurd.

In light of this observation, we define

Since contains precisely many chips, we see from that cannot contain more than many chips. Moreover, more than half of the pairs in are good pairs, and so more than half of the chips in are good chips. We now recurse on .

The procedure described above can be implemented as follows:

"""We identify chips by unique nonnegative integers and assume that
chip_table, an immutable two-dimensional list of numbers, is given.
To see what a testing chip ("testing") has to say about another chip
("tested"), we call chip_table[testing][tested], which returns
True for 'good', and False for 'bad'.

We record the chips to be tested in a list of numbers called chip_list.
chip_list is changed at each recursive step to track the progress.
"""

def get_a_good_chip(chip_table, chip_list):
    n = len(chip_list)

    if n <= 2:
        return chip_list[0]

    if n % 2 != 0:  # if length mod 2 is not zero, i.e., odd
        chip_list = chip_list[:-1]  # cut out the last element
        n = n-1

    m = n//2
    list_x, list_y = chip_list[:m], chip_list[m:]

    keep = []
    for i in range(m):
        x, y = list_x[i], list_y[i]
        if chip_table[x][y] and chip_table[y][x]:  # if both return True
            keep.append((x, y))

    new_chip_list = [pair[0] for pair in keep]

    return get_a_good_chip(chip_table, new_chip_list)
>>> # chips 1, 2, 3 are good
>>> chip_table = [[True, False, True, False, True],
...               [False, True, True, True, False],
...               [False, True, True, True, False],
...               [False, True, True, True, False],
...               [True, False, False, False, True]]
>>> get_a_good_chip(chip_table, [0, 1, 2, 3, 4])
1
>>> # chips 2, 3, 4, 5 are good
>>> chip_table = [[True, True, False, False, False, False],
...               [True, True, False, False, False, False],
...               [False, False, True, True, True, True],
...               [False, False, True, True, True, True],
...               [False, False, True, True, True, True],
...               [False, False, True, True, True, True]]
>>> get_a_good_chip(chip_table, [0, 1, 2, 3, 4, 5])
2

Problem 4-5c

Once one good chip is found, it suffices to test all chips against the good chip to identify all good chips. This takes pairwise tests and can be implemented as follows:

def get_all_good_chips(chip_table):
    n = len(chip_table)
    testing = get_a_good_chip(chip_table, range(n))

    good_chips = [tested for tested in range(n)
                  if chip_table[testing][tested]]

    return good_chips
>>> # chips 1, 2, 3 are good
>>> chip_table = [[True, False, True, False, True],
...               [False, True, True, True, False],
...               [False, True, True, True, False],
...               [False, True, True, True, False],
...               [True, False, False, False, True]]
>>> get_all_good_chips(chip_table)
[1, 2, 3]
>>> # chips 2, 3, 4, 5 are good
>>> chip_table = [[True, True, False, False, False, False],
...               [True, True, False, False, False, False],
...               [False, False, True, True, True, True],
...               [False, False, True, True, True, True],
...               [False, False, True, True, True, True],
...               [False, False, True, True, True, True]]
>>> get_all_good_chips(chip_table)
[2, 3, 4, 5]

The time complexity of get_all_good_chips is

where the time complexity of get_a_good_chip is

The master theorem now implies that

whence it follows that

4-6. Monge arrays

An array of real numbers is a Monge array if for all , , , and such that and , we have

In other words, whenever we pick two rows and two columns of a Monge array and consider the four elements at the intersection of the rows and the columns, the sum of the upper-left and lower-right elements is less than or equal to the sum of the lower-left and upper-right elements. For example, the following array is Monge.

a. Prove that an array is Monge if and only if for all and , we have

(Hint: For the “if” part, use induction separately on rows and columns.)

b. The following array is not Monge. Change one element in order to make it Monge. (Hint: Use part(a))

c. Let be the index of the column containing the leftmost minimum element of row . Prove that for any Monge array.

d. Here is a description of a divide-and-conquer algorithm that computes the leftmost minimum element in each row of an Monge array :

Construct a submatrix of consisting of the even-numbered rows of . Recursively determine the leftmost minimum for each row of . Then compute the leftmost minimum in the odd-numbered rows of .

Explain how to compute the leftmost minimum in the odd-numbered rows of (given that the leftmost minimum of the even-numbered rows is known) in time.

e. Write the recurrence describing the running time of the algorithm described in part (d). Show that its solution is .

Notational remark

As stated in the preface, we shall use the 0-first indexing convention for this problem.

Problem 4-6a

If is Monge, it suffices to pick and .

We suppose that

for all and .

We fix and and show that

for all and .

Observe that is the case. We let , fix , and assume inductively that

for all . By the inductive hypothesis,

implies that

whence it follows that

as was to be shown. This establishes for all and .

We now fix and and assume inductively that

for all . By the inductive hypothesis,

The case of implies that

whence it follows that

as was to be shown. This establishes in full generality.

follows at once from .

Problem 4-6b

The following code tests whether a two-dimensional NumPy array is Monge, using the criterion developed in 4-6a:

"""A is assumed to be a two-dimensional NumPy array.

- The syntax for referencing an entry of A is A[i, j].
- A.shape returns (m, n), the size of the matrix.
"""


def test_monge(A):
    """Check if A is a Monge array using the equivalent definition
    derived in 4-6a"""
    num_rows, num_cols = A.shape
    failed = []
    for i in range(num_rows-1):
        for j in range(num_cols-1):
            if A[i, j]+A[i+1, j+1] > A[i, j+1]+A[i+1, j]:
                failed.append((i, j))

    if not failed:
        print("Monge")
        is_monge = True
    else:
        print("Not Monge")
        print("Failed coordinates: ")
        for pair in failed:
            print(pair)
        is_monge = False
    return is_monge
>>> test_monge(np.array([[10, 17, 13, 28, 23],
...                      [17, 22, 16, 29, 23],
...                      [24, 28, 22, 34, 24],
...                      [11, 13,  6, 17,  7],
...                      [45, 44, 32, 37, 23],
...                      [36, 33, 19, 21,  6],
...                      [75, 66, 51, 53, 34]])
Monge
>>> test_monge(np.array([[37, 23, 22, 32],
...                      [21,  6,  7, 10],
...                      [53, 34, 30, 31],
...                      [32, 13,  9,  6],
...                      [43, 21, 15,  8]])
Not Monge
Failed coordinates:
(0, 1)

As the program suggests, the inequality

fails to hold, as

Since we have

we can add up to 7 to without breaking the inequality

We therefore assign

at which point we obtain

while maintaining

Since the modification affects no other inequality, the resulting array is Monge.

>>> test_monge(np.array([[37, 23, 29, 32],
...                      [21,  6,  7, 10],
...                      [53, 34, 30, 31],
...                      [32, 13,  9,  6],
...                      [43, 21, 15,  8]])
Monge

Problem 4-6c

Let be an Monge array. We fix and assume for a contradiction that

on . Since

we see that the inequality

can never hold unless it is also the case that

Since is the index of the column containing the leftmost minimum element of row , implies that we must always have

rendering the identity

false. We thus conclude that

Since the choice of was arbitrary, the desired result now follows.

Problem 4-6d

We assume that the values of are known. We have seen in 4-6c that

for all . Since we must examine at least one integer for each row, the number of integers we must examine to compute is bounded above by

It then follows that the number of integers we must examine for all the odd rows is bounded above by

We now observe that

whence the desired result follows.

Problem 4-6e

We begin by observing that a submatrix of a Monge array consisting of the rows of is a Monge array. This, in particular, implies that the ordering relation proved in 4-6c continues to hold on such submatrices.

The algorithm for computing the leftmost minimum of each row of a Monge array can be implemented as follows:

"""A is assumed to be a two-dimensional NumPy array.

- The syntax for referencing an entry of A is A[i, j].
- A.shape returns (m, n), the size of the matrix.
- A[::2,:] is the submatrix consisting of the even rows of A.
  0, k, 2k, 3k, and so on.
"""


def find_left_min(A):
    if not test_monge(A):
        return None
    num_rows, num_cols = A.shape
    mins = [0 for _ in range(num_rows)]  # initialize array of length A.shape[0]
    return lm_recursion(A, mins)


def min_index(row, start_index, end_index):
    """Scan a row from start_index to end_index-1 to find the
    index of the leftmost minimum element in the specified range.
    """
    min_ind = start_index
    for i in range(start_index, end_index):
        if row[i] < row[min_ind]:
            min_ind = i
    return min_ind


def lm_recursion(A, mins):
    num_rows, num_cols = A.shape
    if num_rows == 1:  # if A has only one row, use the min_index scan
        mins[0] = min_index(A[0], 0, num_cols)
    else:
        ## take the even rows and recurse
        evens = A[::2, :]
        even_mins = lm_recursion(evens, mins[::2])
        ## even rows have already been computed;
        ## use the min_index scan in the range specified by even_mins
        ## to figure out the min index for odd rows.
        start_index = 0
        for i in range(num_rows):
            if i % 2 == 0:
                mins[i] = even_mins[i//2]
            else:
                left = mins[i-1]
                right = even_mins[(i+1)//2]+1 if i+1 < num_rows else num_cols
                mins[i] = min_index(A[i], left, right)
    return mins
>>> find_left_min(np.array([[10, 17, 13, 28, 23],
...                         [17, 22, 16, 29, 23],
...                         [24, 28, 22, 34, 24],
...                         [11, 13, 6,  17, 7 ],
...                         [45, 44, 32, 37, 23],
...                         [36, 33, 19, 21, 6 ],
...                         [75, 66, 51, 53, 34]))
[0, 2, 2, 2, 4, 4, 4]
>>> find_left_min(np.array([[37, 23, 29, 32],
...                         [21,  6,  7, 10],
...                         [53, 34, 30, 31],
...                         [32, 13,  9,  6],
...                         [43, 21, 15,  8]]))
[1, 1, 2, 3, 3]

What is the running time of find_left_min, where is the number of rows? For the purpose of this discussion, let us focus on analyzing lm_recursion.

Let be an array, so that num_rows == m and num_cols == n. If , then the running time of lm_recursion is precisely that of min_index. Since min_index scans through each column once, we see that the running time is . We thus declare

As for the case, we observe that lm_recursion consists of three steps:

  1. Construct evens, the subarray of even rows, from .
  2. Recurse on evens.
  3. Go through the rows and compute mins.

Since is never modified throughout lm_recursion, there is no need to copy the data of to construct evens, which becomes in the recursive step. The construction of even thus reduces to collecting pointers to the even rows, which can be done in time.

The recursion step is invoked on evens, an array of rows. Since the recursion step is invoked precisely once without any additional procedure, it takes time to run.

Finally, we have shown in 4-6d that the computation of mins takes time. It follows that the running time of lm_recursion is

Since we do not know what is in relation to , we cannot apply the master theorem. Observe, however, that

Since

for all choices of , we see that

We have shown above that , and so

Let us now prove the above estimate by induction. To this end, we fix and choose constants such that

for all choices of .

Let us first establish the upper bound

Fix and assume inductively that

for all , where are constants to be chosen.

Observe that

So long as

we have

The above condition is satisfied precisely when

To establish the base case , we only need the hypothesis

Indeed, this leads to

We thus choose

so that is trivially established, and that

thereby establishing . It now follows from induction that

It remains to establish the lower bound

We fix and assume inductively that

for all , where are constants to be chosen. Observe that

In order to obtain

we must have

and

Observe that the second inequality, along with the added hypothesis that

implies

which is precisely the first inequality. The inductive step thus holds true so long as

To establish the base case , we only need the hypothesis

Indeed, this leads to

We therefore choose

so that and follow. We now conclude by induction that

which, along with the upper bound established above, implies

as was to be shown.

Additional remarks and further results

Generalizations of the master method

The master method does not apply to divide-and-conquer problems with multiple subproblems of substantially different sizes. For example,

is not covered by the master method.

Mohamad Akra and Louay Bazzi, in their 1996 paper “On the Soluton of Linear Recurrence Equations,” present a generalization of the master method that is applicable to recurrence relations of the form

with minor restrictions on . The solution is given by the formula

where is the unique real number that satisfies the identity

For the above example, we have , and so

Using the Akra—Bazzi method, we can also solve more complicated recurrence relations like

In this case, we have

and so the solution to the recurrence relation is

There are, of course, several generalizations beside the Akra—Bazzi method. We refer the reader to Chee Yap’s 2011 paper, “A real elementary approach to the master recurrence and generalizations.”

Generating functions

We have discussed briefly in Problem 4-4 the generating-function technique of solving recurrence relations. We pursue the subject further here, following the treatment in Chapter 3 of Sedgewick/Flajolet.

Given a sequence , we construct its ordinary generating function

and its exponential generating function

The generating-function method of solving recurrences typically involves multiplying both sides of the recurrence by ( for exponential generating functions), summing on , manipulating the resulting identity to derive an explicit formula for the generating function, and computing the power-series expansion of the generating function.

Take, for example,

with the initial condition , , . We multiply both sides by , sum over , and reindex the sums to obtain the identity

For notational simplicity, we let

the ordinary generating function of . Observe that

We can use the above computation to simplify as follows:

Using the initial condition , , , we conclude that

Taking the partial fraction decomposition, we obtain

We now recall that

from which we conclude that

It follows that

for all .

We shall revisit the method of generating functions in later chapters, as more sophisticated recurrence relations arise.