# CLRS Chapter 4. Divide and Conquer

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 $A$ 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 $A$ whenever $A$ 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 $A$ 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 $A$. 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 $A$, as was to be shown. $\square$

4.1-2. Write pseudocode for the brute-force method of solving the maximum-subarray problem. Your procedure should run in $\Theta(n^2)$ 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 $O(n^2)$. It follows that maximal_subarray_brute_force runs in $\Theta(n^2)$ time. $\square$

4.1-3. Implement both the brute-force and recursive algorithms for the maximum-subarray problem on your own computer. What problem size $n_0$ 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 $n_0$. 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. $\square$

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)

$\square$

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 $j+1$ 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 $1 \leq i \leq j+1$. Determine a maximum subarray of the form A[i..j+1] in constant time based on knowing a maximum subarray ending at index $j$.

We fix an index $j \geq 1$ and suppose that $A[p:q]$ is a maximum subarray of $A[:j]$. We pick another index $i$ such that

By the maximality of $A[p:q]$ in $A[:j]$, every maximum subarray of $A[:j+1]$ must either equal to $A[p:q]$ or contain $A[j]$. Now,

whence we conclude that

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

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

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)
(43, 7,1 0)

$\square$

## 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

Observe first that

The product is

$% $ $\square$

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.]]

$\square$

4.2-3. How would you modify Strassen’s algorithm to multiply $n \times n$ matrices in which $n$ is not an exact power of 2? Show that the resulting algorithm runs in time $\Theta(n^{\log 7})$.

For each $n \times n$ matrix $A$, we let $m$ be the unique integer such that $% $ and augment $A$ with an $(2^m - n) \times (2^m - n)$ identity matrix $I$ as follows:

We then have

from which we can extract $AB$ in constant time. It thus suffices to compute the time complexity of the matrix multiplication $\tilde{A} \tilde{B}$.

Observe that

by the monotonicity of $t \mapsto t^{\log 7}$. Similarly,

Now,

and so

It follows that $n^{\log 7} = \Theta((2^m)^{\log 7})$, whence applying Strassen’s algorithm to the augmented matrices does not incur any additional asymptotic time complexity. $\square$

4.2-4. What is the largest $k$ such that if you multiply $3 \times 3$ matrices using $k$ multiplications (not assuming commutativity of multiplication), then you can multiply $n \times n$ matrices in time $o(n^{\log 7})$? What would be the running time of this algorithm be?

The recurrence relation to solve is

Observe that $n^2 = \Theta(n^{\log_3 9})$. By the master theorem ($\S4.5$), we have

where $(\ast)$ is $k > 9$ and $k(n/3)^2 \leq cn^2$ for some $% $ and all sufficiently large $n$.

Since $\log 7 > \log_3 k$ implies that $% $, we see that $T(n) = o(n^{\log 7})$ whenever $k \leq 9$. On the other hand, if $k > 9$, then then inequality

never holds for any $n \geq 1$ reagrdless of which $% $ we choose. It follows that we must have $k \leq 9$ in order to multiply $n$-by-$n$ matrices in time $o(n^{\log 7})$, and the running time is

4.2-5. V. Pan has discovered a way of multiplying $68 \times 68$ matrices using 132,464 multiplications, a way of multiplying $70 \times 70$ matrices using 143,630 multiplications, and a way of multiplying $72 \times 72$ 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 $n^2 = \Theta(n^{\log_{68} 4624}){}_{}$, we invoke the master theorem ($\S4.5$) to conclude that

Since $n^{\log 7} \approx 2.807$, we conclude that $T_{68}{}_{}$ is better than the running time of Strassen.

Observe now that $n^2\Theta(n^{\log_{70} 4900}){}_{}$. The master theorem ($\S4.5$) implies that

Similarly as above, we conclude that $T_{72}{}_{}$ is better than the running time of Strassen.

Finally, we observe that $n^2 = \Theta(n^{\log_{72} 1944}){}_{}$, which implies that

by the master theorem ($\S4.5$). Similarly as above, we conclude that $T_{72}{}_{}$ is better than the running time of Strassen.

We conclude that

where $T_{S}{}_{}$ refers to the runing time of Strassen. $\square$

4.2-6. How quickly can you multiply a $kn \times n$ matrix by an $n \times kn$ 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 $kn \times n$ matrix by an $n \times kn$ matrix through $k^2$ iterations of Strassen. It follows that the computation takes $\Theta(k^2n^{\log 7})$.

Similarly, we use block matrix multiplication

we can multiply an $n \times kn$ matrix by a $kn \times n$ matrix through $k$ iterations of STrassen. It follows that the computation takes $\Theta(k n^{\log 7})$. $\square$

4.2-7. Show how to multiply the complex numbers $a + bi$ and $c + di$ using only three multiplcations of real numbers. The algorithm should take $a$, $b$, $c$, and $d$ as input and produce the real component $ac - bd$ and the imaginary component $ad + bc$ separately.

We set $P_1 = ac$, $P_2 = bd$, and $P_3 = (a+b)(c+d)$. Observe that

and that

It follows that

which only requires three real multiplications.

This algorithm is commonly known as the Karatsuba algorithm. $\square$

## The substitution method for solving recurrences

### Exercises

4.3-1. Show that the solution of $T(n) = T(n-1) + n$ is $O(n^2)$.

We let $C > 0$ be an arbitrary constant, to be chosen later. We fix a postive integer $n$ and assume that

for all $% $. We shall show that

Observe that

By choosing $C = 1$, we see that $-2(C-1)n = 0$ for all $n \geq 0$, from which it follows that

as was to be shown.

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

Since $C = 1$, it suffices to find $m_0$ such that

Choosing any $m_0 \geq \sqrt{2T(1)}$, we see that

as was to be shown. The desired result now follows from mathematical induction with base case $n = m_0$. $\square$

4.3-2. Show that the solution of $T(n) = T(\lceil n/2 \rceil) + 1$ is $O(\log n)$.

We first examine the recurrence for $n \geq 2$.

We let $C > 0$ be an arbitrary constant, to be chosen later. We fix a positive integer $n$ and assume that

for all $% $. We shall show that

Observe that

We can bound the last expression by $C \log n$ if and only if

The above inequality is equivalent to

Recalling that $n \geq 2$, we note that

Choosing $C = 1/(1 + \log(2/3))$, 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 $k \geq 1.$ Since $C = 1/(1 + \log(2/3))$, it suffices to find $k_0$ such that

The above inequality is equivalent to

which, in turn, is equivalent to

We pick any $k_0$ that satisfies the last inequality and set $m_0 = 2^{k_0}$, so that

The desired result now follows from mathematical induction with base case $n = m_0$. $\square$

4.3-3. We saw that the solution of $T(n) = 2T(\lfloor n/2 \rfloor) + n$ is $O(n \log n)$. Show that the solution of this recurrence is also $\Omega(n \log n)$. Conclude that the solution is $\Theta(n \log n)$.

We first examine the recurrence for $n \geq 2$.

We let $C > 0$ be an arbitrary constant, to be chosen later. We fix a positive integer $n$ and assume that

for all $% $. We shall show that

Observe that

The inequality

is equivalent to

which, in turn, is equivalent to

Since $n \geq 2$, we see that

We claim that the function

is monotonically decreasing on $[2,\infty)$. Indeed, we have that

from which we conclude that $f(k) > f(k+1)$. Monotonicity now follows.

The monotonicity of $f(k)$ implies that

Setting $C = \frac{2}{3}$, we see that $(\ast \ast)$ holds, whence $(\ast)$ holds. We conclude that

with this choice of $C$, as was to be shown.

To turn the above argument into a complete induction proof, we observe that $m_0 = 2$ yields

as $T$ is typically assumed to be nonnegative.

The desired result now follows from mathematical induction with base case $n =m_0$.

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

Recall (4.19):

We let $C > 0$ be an arbitrary constant, to be chosen later. We fix a positive integer $n$ and assume that

for all $% $. We shall show that

Observe that

$C \geq T(1) - 1$, we have $1-C \leq -T(1)$, 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 $n=1$. $\square$

4.3-5. Show that $\Theta(n \log n)$ is the solution to the “exact” recurrence (4.3) for merge sort.

Recall (4.3):

We let $c > 0$ and $C > 0$, to be chosen later. We fix a positive integer $n$ and assume that

for all $% $. We shall show that

Since $T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + \Theta(n)$, we have the double-ended estimate

where the constants $d > 0$ and $D > 0$ are to be chosen later.

We first establish the upper bound. Since $\lfloor n/2 \rfloor \leq \lceil n/2 \rceil$,

$\lceil n/2 \rceil \geq n/2$, and so $n/\lceil n/2 \rceil \leq n/(n/2) = 2$. It then follows that

whence any choice of $C$ and $D$ with $C \leq D$ yields

Let us now establish the lower bound. Since $\lceil n/2 \rceil \geq \lfloor n/2 \rfloor$,

$\lfloor n/2 \rfloor \leq n/2$, and so $n/\lfloor n/2 \rfloor \geq n/(n/2) = 2$. It then follows that

whence any choice of $c$ and $d$ with $c \leq d$ 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 $c = d = T(2)/4$ and $C = D = 2T(2)$ and observe that, for $n = 2$,

and that

It follows from mathematical induction that $T(n) = \Theta(n \log n)$ with base case $n = 2$. $\square$

4.3-6. Show that the solution to $T(n) = 2T(\lfloor n /2 \rfloor + 17) + n$ is $O(n \log n)$.

Assume that $n \geq 68$, so that $17 \leq n/4$.

We let $C > 0$, to be chosen later. We fix a positive integer $n$ and assume that

for all $% $. We shall show that

Observe that

Now, $n \geq 68$, and so

and

It follows that

Since $\log(4/3) > 0$, we have $% $, and so

It thus suffices to pick $C > 0$ such that

keeping in mind that $n \geq 68$. Since $n$ and $\log n$ are both positive under this condition, we need only to pick $C$ large enough that

Letting $C = 1/\log(4/3)$, 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 $n = 68$ that

as was to be shown. $\square$

4.3-7. Using the master method in Section 4.5, you can show that the solution to the recurrence $T(n) = 4T(n/3) + n$ is $T(n) = \Theta(n^{\log_3 4})$. Show that a substitution proof with the assumption $T(n) \leq cn^{\log_3 4}$ 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 $n \geq 1$, the substitution argument fails.

for all $% $, then

and the usual substitution proof goes through. $\square$

4.3-8. Using the master method in Section 4.5, you can show that the solution to the recurrence $T(n) = 4T(n/2) + n$ is $T(n) = \Theta(n^2)$. Show that a substitution proof with the assumption $T(n) \leq cn^2$ fails. Then show how to subtract off a lower-order term to make a substitution proof work.

Since $c(n/2)^2 = (c/4)n^2$, a naïve substitution argument would yield

which is larger than $cn^2$ for all $n \geq 1$.

for all $% $, then

and the usual substitution proof goes through. $\square$

4.3-9. Solve the recurrence $T(n) = 3T(\sqrt{n}) + \log n$ by makign a change of variables. Your solution should be asymptotically tight. Do not worry about whether values are integral.

Since

we set $S(m) = T(2^m)$ and solve instead

The master theorem ($\S4.5$) shows that

We shall show this by substitution.

We let $c > 0$ and $C > 0$, to be chosen later. We fix a positive integer $n$ 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 $c = C = S(1) + 2$, we see that

and that

Mathematical induction with base case $m = 1$ now shows that

for all $m \geq 1$. Since the lower bound agreed with the upper bound, we in fact have the identity

Since $T(n) = S(\log n)$, 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 $T(n) = 3T(\lfloor n/2 \rfloor) + n$. Use the substitution method to verify your answer.

Observe that

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

for all $% $. We shall show that

Indeed,

To complete the induction proof, we must show that

We set $C = T(1) + 2$ and observe that

as was to be shown. It now follows from mathematical induction with base case $n = 1$ that $T(n) = O(n^{\log(3/2)})$. $\square$

4.4-2. Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = T(n/2) + n^2$. Use the substitution method to verify your answer.

Observe that

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

for all $% $. We shall show that

Observe that

So long as $C \geq 4$, we have $C/4 + 1 \leq C$, and so

To complete the induction proof, we must show that

To this end, we simply select $C = \max(4, T(1))$. The desired result now follows from induction. $\square$

4.4-3. Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = 4T(n/2 + 2) + n$. 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 $T$ is a function defined on $\mathbb{N}$. To remedy this issue, we shall consider instead

Observe that

Setting $n = 2^k$, we obtain

We therefore conjecture that

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

We let $C > 0$ and $D > 0$, to be chosen later. We fix a positive integer $n$ and assume that

for all $% $. We shall show that

Observe that

If we choose $C$ and $D$ so that $4C -D + 1 \leq 0$ and $8C - 6D \leq 0$, then we have the bound

How do we choose such $C$ and $D$? 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 $n_0$. Since the smallest $D$ that satisfies $(\ast)$ is $4C + 1$, the base case should be chosen so that $Cn_0^2 - (4C+1)n_0 > 0$. This only works if $n_0 \geq 5$. indeed, if $n_0 = 4$, then

On the other hand, if $n_0 = 5$, then

which is positive if $C > 4/5$.

Summarizing the above argument, we choose $C = T(5) + 1$ and $D = 4T(5) + 5$. For the base case $n = 5$, we have

as $T$ is generallly assumed to be nonnegative.

We now assume inductively that

holds for all $% $ such that $m \geq 5$. Now, the inductive hypothesis implies that

as was to be shown. We conclude that $T(n) = O(n^2)$. $\square$

4.4-4. Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = 2T(n-1) + 1$. Use the substitution method to verify your answer.

Observe that

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

for all $% $. We then have

By choosing $C = T(1)/2$, we have

for $n = 1$. It now follows from mathematical induction that $T(n) = O(2^n)$. $\square$

4.4-5. Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = T(n-1) + T(n/2) + n$. Use the substitution method to verify your answer.

To make sense of the $n/2$ term, we consider instead

Since $T(n) - T(n-1) = T(\lfloor n/2 \rfloor) + n$, we see that

Therefore,

Applying $(\ast)$ to the sum indexed by $i_1$, we obtain

Applying $(\ast)$ recursively, we obtain

Let us verify our guess. To this end, we let $C > 0$ and $D > 0$, to be chosen later. We fix a positive integer $n$ 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 $n \geq 1$. This holds when $C \geq 2 + 2D$:

Finally, we must pick $C$ and $D$ so that

holds when $n = 1$. This requires

Setting $D = T(1)$ and $C = 2T(1) + 2$, we see that

The choice of $C$ and $D$ also shows that

whenever

for all $% $. It now follows from mathematical induction with base case $n = 1$ that $T(n) = O(n^{\log n})$. $\square$

4.4-6. Argue that the solution to the recurrence $T(n) = T(n/3) + T(2n/3) + cn$, where $c$ is a constant, is $\Omega(n \log n)$ by appealing to a recursion tree.

Observe that

where $\begin{pmatrix} p \\q \end{pmatrix} = \frac{p!}{q!(p-q)!}$ is the binomial coefficient with respect to $(p,q)$. It follows that $T(n) = \Omega(n \log n)$. $\square$

4.4-7. Draw the recursion tree for $T(n) = 4T(\lfloor n/2 \rfloor) + cn$, where $c$ 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 $T(n) = \Theta(n^2)$.

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

for all $% $. We shall show that

Observe that

Therefore, $D$ must be chosen so that $(c-D)n +2 \leq 0$ for all $n \geq 1$. This holds if $D \geq c + 2$.

We now set

and

so that

Moreover, if $T(m) \leq Cm^2 - Dm$ for all $% $, then

It now follows from induction with base case $n = 1$ that $T(n) = O(n^2)$.

It remains to show that $T(n) = \Omega(n^2)$.

We let $C > 0$ and $D > 0$, to be chosen later. We fix a positive integer $n$ and assume that $T(m) \geq Cm^2 + Dm$ for all $% $. Observe that

To ensure that the resulting expression is bounded below by $Cn^2 + Dn$, we must at least have $D-2C+c > 0$. This holds if $D > 2C - c$.

We assume for now that $c > 0$ and set $C = \min(c/2, T(1)/2)$ and $D = \min(c/4, T(1)/4)$, so that

Moreover,

and so it follows from mathematical induction with base case $n=1$ that $T(n) = \Omega(n^2)$.

We have thus shown that $T(n) = \Theta(n^2)$. $\square$

4.4-8. Use a recursion tree to give an asymptotically tight solution to the recurrence $T(n) = T(n-a) + T(a) + cn$, where $a \geq 1$ and $c > 0$ are constants.

Observe that

We thus conjecture that $T(n) = \Theta(n^2)$.

Since $% $ for $% $, the recurrence relation cannot hold for $% $. We thus assume that the values of $T$ for $n = 1,\ldots,\lfloor a \rfloor$ are given.

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

for all $n \geq 2 \lfloor a \rfloor$. We first assume that $C \geq T(\lfloor a \rfloor) / (\lfloor a \rfloor)^2$, so that $(\ast)$ holds for $n = \lfloor a \rfloor$.

Observe that

If $C \geq c/(2 \lfloor a \rfloor)$, then

and so

We thus assume that

We now fix $n_0 > 2\lfloor a \rfloor$ and assume that $(\ast)$ holds for $% $. We shall show that $(\ast)$ holds for $n = n_0$.

Observe that

If $C \geq c$, then

Since $a \geq 1$, we have the estimate

Now, $n_0 > 2 \lfloor a \rfloor$, and so

It follows that $(\ast)$ holds for $n = n_0$ whenever $C \geq c$.

Setting

we see that $(\ast)$ holds for all $n \geq 2 \lfloor a \rfloor$. It follows that $T(n) = O(n^2)$.

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

for all $n \geq 2 \lfloor a \rfloor$. We first assume that $C \leq T(\lfloor a \rfloor) / (\lfloor a \rfloor)^2$, so that $(\ast \ast)$ holds for $n = \lfloor a \rfloor$.

Observe that

If $C \leq c/(2 \lfloor a \rfloor)$, then

and so

We thus assume that

We now fix $n_0 > 2\lfloor a \rfloor$ and assume that $(\ast \ast)$ holds for $% $. We shall show that $(\ast\ast)$ holds for $n = n_0$.

Observe that

If $C \leq c/2a$, then

Since $a \geq 0$, we have $2ac^2 \geq 0$, and so

It follows that $(\ast \ast)$ holds for $n = n_0$ whenever $C \leq c/2a$.

Setting

we have $(\ast \ast)$ for all $n \geq 2 \lfloor a \rfloor$. It follows that $T(n) = \Omega(n^2)$.

We now conclude that $T(n) = \Theta(n^2)$, as was to be shown. $\square$

4.4-9. Use a recursion tree to give an asymptotically tight solution to the recurrence $T(n) = T(\alpha n) + T((1-\alpha) n) + cn$, where $\alpha$ is a constant in the range $% $ and $c > 0$ is also a constant.

Observe that

We let $a = \max(\alpha, 1-\alpha)$ and set $p = \lceil \log_{1/\alpha} n \rceil$, so that

for all $0 \leq i \leq p$. The recursion-tree computation yields

We therefore conjecture that $T(n) = \Theta(n \log n).$

We first establish the upper bound. To this end, we let $C > 0$, 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 $T(2) \leq C n \log n$, and that

whenever $T(m) \leq Cm \log m$ for all $% $. It now follows from induction that $T(n) = O(n \log n)$.

We now establish the lower bound. To this end, we let $C > 0$, 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 $T(2) \geq C n \log n$, and that

whenever $T(m) \geq Cm \log m$ for all $% $. It now follows from induction that $T(n) = \Omega(n \log n)$.

We have thus shown that $T(n) = \Theta(n \log n)$. $\square$

## 4.5. The master method for solving recurrences

### The master theorem, as stated in CLRS, Theorem 4.1

Let $a \geq 1$ and $b > 1$ be constants, let $f(n)$ be a function, and let $T(n)$ be defined on the nonnegative integers by the recurrence

where we interpret $n/b$ to mean either $\lfloor n /b \rfloor$ or $\lceil n/b \rceil$. Then $T(n)$ has the following asymptotic bounds:

1. If $f(n) = O(n^{\log_b a - \epsilon})$ for some constant $\epsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$.
2. If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \log n)$.
3. If $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some constant $\epsilon > 0$, and if $a f(n/b) \leq cf(n)$ for some constant $% $ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$.

### Exercises

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

a. $T(n) = 2T(n/4) + 1$.

b. $T(n) = 2T(n/4) + \sqrt{n}$.

c. $T(n) = 2T(n/4) + n$.

d. $T(n) = 2T(n/4) + n^2$.

a belongs to case 1, and so

b belongs to case 2, and so

c belongs to case 3, as

for all $n$. Therefore,

d belongs to case 3, as

for all $n$. 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 $n/4 \times n/4$, and the divide and combine steps together will take $\Theta(n^2)$ time. He needs to determine how many subproblems his algorithm has to create in order to beat Strassen’s algorithm. If his algorithm creates $a$ subproblems, then the recurrence for the running time $T(n)$ becomes $T(n) = aT(n/4) + \Theta(n^2)$. What is the largest integer value of $a$ for which Professor Caesar’s algorithm would be asymptotically faster than Strassen’s algorithm?

We recall that Strassen’s time complexity is $\Theta(n^{\log_2 7})$. In light of this, it suffices to find the maximum integral value of $a$ such that

subject to the restriction that $f(n) = n^2$ is asymptotically smaller than $n^{\log_b a}$.

Since $b = 4$, the restriction yields the lower bound

Observe that $\log_4 x = \log_2 7$ is equivalent to

which, in turn, is equivalent to

Since $\log_4 2 = 1/2$, we conclude that

It follows that we must have $% $, whence the optimal integral value of $a$ is $48$. $\square$

4.5-3. Use the master method to show that the solution to the binary-search recurrence $T(n) = T(n/2) + \Theta(1)$ is $\Theta(\log n)$. (See Exercise 2.3-5 for a description of binary search.)

Since $a = 1$ and $b = 2$, we have $\log_b a = 0$. Therefore, $f(n) = \Theta(1)$ is asymptotically equivalent to $n^{\log_b a}$, whence the master method implies that

as was to be shown. $\square$

4.5-4. Can the master method be applied to the recurrence $T(n) = 4T(n/2) + n^2 \log n$? Why or why not? Give an asymptotic upper bound for this recurrence.

The $\log n$ term in $f(n) = n^2\log n$ makes it impossible to apply the master method here. $\log_b a = 2$, so $f(n) = \Omega(n^{\log_b a})$. Nevertheless, $\log n = o(n^p)$ for all $p > 0$, and so $f(n) = O(n^{\log b (a + \epsilon)})$ for all $\epsilon > 0$. It follows that none of the three cases of the master method is applicable.

We shall compute the recursion tree of $T(n)$. Observe:

Since

we conjecture that

To show this, we let $C > 0$, to be chosen later. We assume that

for all $% $. (We pick 16, so that $\log n > 4$.) We shall show that

Observe that

Since $\log n > 4$, we have

whenever $C \geq 1$.

We now set

so that, for $n = 16$,

Moreover, $C \geq 1$, and so

for all $% $

implies

It now follows from induction that $T(n) = O(n^2(\log n)^2)$. $\square$

4.5-5. Consider the regularity condition $af(n/b) \leq cf(n)$ for some constant $% $, which is part of case 3 of the master theorem. Give an example of constants $a \geq 1$ and $b > 1$ and a function $f(n)$ 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 $a \geq 1$, $b > 1$, $C > 0$, and $\epsilon > 0$ be arbitrary, and let

Since

we see that setting $c = a/(a+\epsilon)$ yields

for all $n \in \mathbb{N}$. $\epsilon > 0$, and so $% $.

This suggests that we need an oscillating term. Let us pick $a = 1$, $b = 2$, and $f(n) = 2n - n\cos(2 \pi n)$. Observe that

Whenever $n$ is odd, $\cos(\pi n) = -1$ and $\cos(2 \pi n) = 1$, and so

It follows that, whenever $% $, the inequality

cannot hold for all $n$. $\square$

## 4.6. Proof of the master theorem

### Exercises

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

We shall prove a more general result: whenever $m,n \in \mathbb{N}$ and $x \in \mathbb{R}$, we have the identity

Observe that

This implies, in particular, that

The upper bound of $(\ast)$ implies that

We suppose for a contradiction that

We can find an integer $p$ such that

This implies that

so that

The lower bound of $(\ast\ast)$ implies that

It now follows from $(\ast\ast)$ that

which is evidently absurd. We conclude that

Let us now recall (4.27):

We shall show that

whenever $b$ is an integer. We proceed by mathematical induction. The $j = 0$ case is trivially true. If the $j = j_0 - 1$ case holds, then $(\ast\ast\ast)$ implies that

as was to be shown. $\square$

4.6-2. Show that if $f(n) = \Theta(n^{\log_b a} \log^k n)$, where $k \geq 0$, then the master recurrence has solution $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$. For simplicity, confine your analysis to exact powers of $b$.

We begin with a remark that

not

Fix $k \geq 0$. Recall from (4.21) that

Since

we see that

It thus suffices to show that

Since $b > 1$,

and so

$(\ast)$ follows from $(\ast\ast)$ if we can prove, in addition, that

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

for all $p \geq 1$, where $C$ is a constant independent of $p$.

We shall prove $(\ast\ast\ast)$ by induction on $p$.

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

for all $% $, where $C > 0$ is a constant to be chosen later. We shall show that

To this end, we observe that

By way of the inductive hypothesis $(\star)$, we bound the above quantity below by

To show $(\star)$, it now suffices to establish the estimate

We write

for each $p$ and observe that

$b > 1$ implies that $\log^k(b) > 0$, and so we need only to show that

The above inequality is equivalent to

as $A_p > 1$ for all sufficiently large $p$. In fact, if $C \geq \frac{1}{\log b}$, then $A_p > 1$ for all $p > 1$.

It thus suffices to establish

If $C = \frac{1}{\log b}$, then

Since $p_0 > 1$, we see that

for all $k \geq 1$, establishing $(\star\star)$ for $C = \frac{1}{\log b}$.

It follows that $(\star)$ holds for $C = \frac{1}{\log b}$, which establishes the inductive case of $(\ast \ast \ast)$.

To complete the proof of $(\ast\ast\ast)$ by induction, we must establish the base case $p = 1$, i.e.,

Since we have chosen $C = \frac{1}{\log b}$, the base case holds with equality. The induction proof is now complete.

Finally, $(\ast)$ follows from $(\ast\ast)$ and $(\ast\ast\ast)$, and we have the desired estimate

Our work here is done. $\square$

4.6-3. Show that case 3 of the master theorem is overstated, in the sense that the regularity condition $af(n/b) \leq cf(n)$ for some constant $% $ implies that there exists a constant $\epsilon > 0$ such that $f(n) = \Omega(n^{\log_b a + \epsilon})$.

We recall from Theorem 4.1 that $a \geq 1$ and $b > 1$. We let $C = \frac{a}{c}$ and observe that the regularity condition can be rewritten as

Applying $(\ast)$ $\lceil \log_b n \rceil$ times, we obtain

Since $\log_b n \leq \lceil \log_b n \rceil$, we have the estimate

Now, $C^{\log_b n} = n^{\log_b C}$, and so

$C = \frac{a}{c}$ implies $\log_b C = \log_b a + \log_b \frac{1}{c}$, and so

where $\epsilon = \log_b \frac{1}{c}$. It follows that

Finally, we remark that $% $ implies $\epsilon > 0$. $\square$

## Problems

### 4-1. Recurrence examples

Give asymptotic upper and lower bounds for $T(n)$ in each of the following recurrences. Assume that $T(n)$ is constant for $n \leq 2$. Make your bounds as tight as possible, and justify your answers.

a. $T(n) = 2T(n/2) + n^4$

b. $T(n) = T(7n/10) + n$

c. $T(n) = 16T(n/4) + n^2$

d. $T(n) = 7T(n/3) + n^2$

e. $T(n) = 7T(n/2) + n^2$

f. $T(n) = 2T(n/4) + \sqrt{n}$

g. $T(n) = T(n-2) + n^2$

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 $a \geq 1$ and $b > 1$ be constants, let $f(n)$ be a function, and let $T(n)$ be defined on the nonnegative integers by the recurrence

where we interpret $n/b$ to mean either $\lfloor n/b \rfloor$ or $\lceil n/b \rceil$. Then $T(n)$ has the following asymptotic bounds:

1. If $f(n) = O(n^{\log_b a - \epsilon})$ for some constant $\epsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$.

2. If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a} \log n)$.

3. If $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some constant $\epsilon > 0$, and if $af(n/b) \leq cf(n)$ for some constant $% $ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$.

#### Problem 4-1a

$a = b = 2$, so that $\log_b a = 1$. Since

$f(n) = \Omega(n^{\log_b a + 3})$ and

we see that

#### Problem 4-1b

$a = 1$ and $b = \frac{10}{7}$, so that $\log_b a = 0$. Since

and

we see that

#### Problem 4-1c

$a = 16$ and $b = 4$, so that $\log_b a = 2$. Since $f(n) = \Theta(n^{\log_b a})$, we see that

#### Problem 4-1d

$a = 7$ and $b = 3$, so that $% $. Since

and

we see that

#### Problem 4-1e

$a = 7$ and $b = 2$, so that $% $. Since

we see that

#### Problem 4-1f

$a = 2$ and $b = 4$, so that $\log_b a = \frac{1}{2}$. Since $f(n) = \Theta(n^{\log_b a})$, 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 $n' = \lfloor n/2 \rfloor$.Since $n' = \Theta(n)$, we have

### 4-2. Parameter-passing costs

Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an $N$-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 = $\Theta(1)$.

2. An array is passed by copying. Time = $\Theta(N)$, where $N$ 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 = $\Theta(q-p+1)$ if the subarray $A[p..q]$ 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 $N$ be the size of the original problem and $n$ 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 $T(N)$ be the worst-case running time of binary_search on a list of length $N$. Since it takes constant time to execute all but the recursive step of the algorithm, we have

where $f(N,n)$ is the time it takes to pass a length-$n$ subarray of an array of length $N$.

If arrays are passed by pointer, then $f(N,n) = \Theta(1)$, and so

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

If arrays are passed by copying, then $f(N,n) = \Theta(N)$, and so

By the master theorem, we have

Finally, if arrays are passed by copying the appropriate subranges, then $f(N,n) = N/n = N/\lfloor N/2 \rfloor$. We thus have $f(N,n) = \Theta(1)$, 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 $\Theta(r-p)$. Since we divide the input array in half, the time complexity of merge_sort is

where $f(a,b)$ is the time it takes to pass a length-$b$ subarray of an array of length $a$.

Since $f(n, n/2) = \Omega(n)$ 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 $T(n)$ in each of the following recurrences. Assume that $T(n)$ is constant for sufficiently small $n$. Make your bounds as tight as possible, and justify your answers.

a. $T(n) = 4T(n/3) + n \log n$.

b. $T(n) = 3T(n/3) + n / \log n$.

c. $T(n) = 4T(n/2) + n^2 \sqrt{n}$.

d. $T(n) = 3T(n/3 - 2) + n/2$.

e. $T(n) = 2T(n/2) + n/\log n$.

f. $T(n) = T(n/2) + T(n/4) + T(n/8) + n$.

g. $T(n) = T(n-1) + 1/n$.

h. $T(n) = T(n-1) + \log n$.

i. $T(n) = T(n-2) + \log n$.

j. $T(n) = \sqrt{n} T(\sqrt{n}) + n$.

See Section 4.5 for the statement of the master theorem.

#### Problem 4-3a

Recall from Problem 3-2 that

for every $\epsilon > 0$. 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 $\epsilon > 0$,

and that

for any choice of $\epsilon > 0$.

Since $\log n \geq 1$ for all $n \geq 2$, we have that

for all $n \geq 2$. This implies $(\ast\ast)$. $(\ast)$ follows from $(\ast)$.

For $(\ast\ast\ast)$, we observe that each constant $C > 0$ furnishes an integer $M_C$ such that

for all $n \geq M_C$. It follows that

for all $n \geq M_C$, and $(\ast\ast\ast)$ follows.

Finally, we recall from Problem 3-2 that

for every $\rho > 0$. This implies that each choice of $\rho > 0$ and $C > 0$ furnishes an integer $N_{\rho, C}$ such that

for all $n \geq N_{\rho, C}$. Therefore, we see that

for all $n \geq N_{\epsilon, C}{}_{}$, and $(\ast\ast\ast\ast)$ follows.

Let us now proceed without the master theorem.

We let $k = \log_3 n$ and observe that

Since $% $, we see that

Moreover, $% $, and so

We thus have the estimates

In order to estimate the sum, we define $f(x) = \frac{1}{k-x}$ and observe that

whenever $i-1 \leq x \leq i$. Therefore,

for any choice of index $i$, whence it follows that

Since $k - \lfloor k \rfloor \geq 0$, we see that

We thus end up with the upper bound

for constants $C$, $D$, and $E$. We conclude that

To establish a lower bound, we set $f(x) = \frac{1}{k-x}$ once againd and observe that

whenever $i \leq x \leq i+1$. Therefore,

for any choice of index $i$, whence it follows that

Since $% $, we see that

We thus end up with the lower bound

for constants $C$ and $D$. 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 $n$, 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 $T(n) = aT(n/b) + f(n)$. If, however, we drop the $-2$ term, we can use the master theorem on

to obtain

Since the $-2$ term shouldn’t affect the asymptotic behavior of $T$, we conjecture that

To prove $(\ast)$, we first fix $n > 6$, so that $\frac{n}{3} - 2 > 1$. Assume inductively that

for all $% $, where $C > 0$ is a constant to be chosen later. Observe that

If we choose $C > \frac{1}{2 \log 3}$, then we have

for all $n \geq 6$, and we have the desired bound

To establish the base case $n=6$, we choose

so that the inductive step continues to holds, while

for $n = 6$. We now conclude by induction that

To prove $(\ast)$, it now remains to show that

To this end, we fix $n > 24$, so that $\frac{n}{3} - 2 > 2$ and $\frac{n}{3} - 2 > \frac{n}{4}$. Assume inductively that

for all $% $, where $C > 0$ is a constant to be chosen later. Observe that

Since $\frac{n}{3} - 2 > \frac{n}{4}$, we have

Choosing $C \leq \frac{1}{8}$ yields

so that

as was to be shown.

To establish the base case $n = 24$, we choose

so that the inductive step continues to hold, while

for $n = 24$. 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 $k = \log_a n$ 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 $k>0$. Since

we conjecture that

To verify this, we fix $n > 8$ and assume inductively that

for all $% $, where $C > 0$ and $D > 0$ are constants to be chosen. Observe that

Analogously,

So long as $C \geq 7$ and $D \leq 7$, 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 $n = 8$, 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 $\log n! = \Theta(n \log n)$, 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 $k!!$ is the double factorial function

We let $m = \lfloor n/2 \rfloor$. If $m$ is even, then

In this case,

which is $\Theta(m \log m) = \Theta(n \log n)$.

If $m$ is odd, then

In this case,

We have proved in Exercise 3.2-3 that $\log k! = \Theta(k \log k)$, and so $\log m!!$ has the asymptotic estimate of $\Theta(m \log m) = \Theta(n \log n)$.

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 $n = 2^m$:

Setting $S(m) = T(2^m)$, we see that

Observe that

Since

we see that $S(m) = \Theta\left( 2^m \log m\right)$.

The identity $m = \log n$ 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) $\mathscr{F}$ as

where $F_i$ is the $i$th Fibonacci number.

a. Show that $\mathscr{F}(z) = z + z \mathscr{F}(z) + z^2 \mathscr{F}(z)$.

b. Show that

where

and

c. Show that

d. Use part (c) to prove that $F_i = \phi^i / \sqrt{5}$ for $i > 0$, rounded to the nearest integer. (Hint: Observe that $% $.)

#### Problem 4-4a

Observe that

We then have

Since $F_0 = F_1 = 1$ and $F_i = F_{i-1} + F_{i-2}$ for all $i \geq 2$, we conclude that

#### Problem 4-4b

It follows at once from 4-4a that

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.) $\square$

#### Problem 4-4c

Page 1147 of CLRS tells us that

Substituting $x = \phi z$, we get

Similarly,

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

#### Problem 4-4d

We have shown in 4-4c that

for all indices $i$. Since $% $, we have

whence it follows that

In other words, $F_i$ is $\phi^i/\sqrt{5}$ rounded to the nearest integer. $\square$

### 4-5. Chip testing

Professor Diogenes has $n$ 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 $A$ says Chip $B$ says Conclusion
$B$ is good $A$ is good both are good, or both are bad
$B$ is good $A$ is bad at least one is bad
$B$ is bad $A$ is good at least one is bad
$B$ is bad $A$ is bad at least one is bad

a. Show that if at least $n/2$ 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 $n$ chips, assuming that more than $n/2$ of the chips are good. Show that $\lfloor n/2 \rfloor$ 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 $\Theta(n)$ pairwise tests, assuming that more than $n/2$ of the chips are good. Give and solve the recurrence that describes the number of tests.

#### Notational Remark

Given two chips $x$ and $y$, we write $T_x(y)$ to denote what $x$ has to say about $y$. The possible outcomes are, of course, good, and bad.

A test consists of inputting two chips $x$ and $y$ and receiving the output $(T_x(y), T_y(x)).$

#### Problem 4-5a

Assume that at least $n/2$ chips are bad. Let $\mathcal{G}$ be the set of all good chips, and let $\mathcal{B}$ be a set of bad chips of size $\vert \mathcal{G} \vert$. We let $\mathcal{R}$ be the remaining chips, if there are any.

Observe that, for each $x \in \mathcal{G}$,

Let us consider the following adversarial strategy: each $x \in \mathcal{B}$ returns

and each $x \in \mathcal{R}$ returns

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

The partition process produces three categories: namely, $\mathcal{G}$, $\mathcal{B}$, and $\mathcal{R}$.

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 $\mathcal{G}$ and $\mathcal{B}$ 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. $\square$

#### Problem 4-5b

Let us assume that more than $n/2$ of the chips are good.

We assume that $n$ is even, and set $m = n/2$. 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, $\mathcal{X} = \{x_1,\ldots,x_m\}$ and $\mathcal{Y} = \{y_1,\ldots,y_m\}$, assigning indices $1,\ldots,m$ arbitrarily.

For each index $i$, we declare the pair $(x_i, y_i)$ to be in the keep pile $\mathcal{K}$ if and only if

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

We also define the discard pile $\mathcal{D}$ to be the collection of all pairs $(x_i,y_i)$ that do not belong to $\mathcal{K}$. We denote by $\vert \mathcal{K} \vert$ and $\vert \mathcal{D} \vert$ the number of pairs in $\mathcal{K}$ and $\mathcal{D}$, respectively. We note here that

Moreover, each pair in $\mathcal{D}$ must contain at least one bad chip, and so

We now observe that $\mathcal{K}$ contains more than $\vert \mathcal{K} \vert /2$ good pairs. Indeed, if $\mathcal{K}$ contained at most $\vert \mathcal{K} \vert / 2$ good pairs, then

which is absurd.

In light of this observation, we define

Since $\mathcal{R}$ contains precisely $\vert \mathcal{K} \vert$ many chips, we see from $(\ast)$ that $\mathcal{R}$ cannot contain more than $n/2 - \vert \mathcal{D} \vert$ many chips. Moreover, more than half of the pairs in $\mathcal{K}$ are good pairs, and so more than half of the chips in $\mathcal{R}$ are good chips. We now recurse on $\mathcal{R}$. $\square$

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 $\Theta(n)$ 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 $S$ of get_all_good_chips is

where the time complexity $T$ of get_a_good_chip is

The master theorem now implies that

whence it follows that

### 4-6. Monge arrays

An $m \times n$ array $A$ of real numbers is a Monge array if for all $i$, $j$, $k$, and $l$ 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 $i=1,2,\ldots, m-1$ and $j=1,2,\ldots,n-1$, 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 $f(i)$ be the index of the column containing the leftmost minimum element of row $i$. Prove that $f(1) \leq f(2) \leq \cdots \leq f(m)$ for any $m \times n$ Monge array.

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

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

Explain how to compute the leftmost minimum in the odd-numbered rows of $A$ (given that the leftmost minimum of the even-numbered rows is known) in $O(m+n)$ time.

e. Write the recurrence describing the running time of the algorithm described in part (d). Show that its solution is $O(m + n \log m)$.

#### Notational remark

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

#### Problem 4-6a

$(\Rightarrow)$ If $A$ is Monge, it suffices to pick $k = i+1$ and $l = j+1$. $\square$

$(\Leftarrow)$ We suppose that

for all $i=1,2,\ldots,m-1$ and $j=1,2,\ldots,n-1$.

We fix $i$ and $j$ and show that

for all $p \geq 1$ and $q \geq 1$.

Observe that $(\ast)$ is the $p = q = 1$ case. We let $q = 1$, fix $p > 1$, and assume inductively that

for all $% $. By the inductive hypothesis,

$(\ast)$ implies that

whence it follows that

as was to be shown. This establishes $(\ast\ast)$ for all $p \geq 1$ and $q = 1$.

We now fix $p > 1$ and $q > 1$ and assume inductively that

for all $% $. By the inductive hypothesis,

The $q =1$ case of $(\ast\ast)$ implies that

whence it follows that

as was to be shown. This establishes $(\ast\ast)$ in full generality.

$(\ast)$ follows at once from $(\ast\ast)$. $\square$

#### 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 $A[0,2]$ 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 $A$ be an $m \times n$ Monge array. We fix $% $ and assume for a contradiction that

on $A$. Since

we see that the inequality

can never hold unless it is also the case that

Since $f(i)$ is the index of the column containing the leftmost minimum element of row $i$, $(\ast)$ implies that we must always have

rendering the identity

false. We thus conclude that

Since the choice of $i$ was arbitrary, the desired result now follows. $\square$

#### Problem 4-6d

We assume that the values of $f(0),f(2),\ldots, f(2 \lfloor (n-1)/2 \rfloor)$ are known. We have seen in 4-6c that

for all $k$. Since we must examine at least one integer for each row, the number of integers we must examine to compute $f(2k+1)$ 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. $\square$

#### Problem 4-6e

We begin by observing that a submatrix $A'$ of a Monge array $A$ consisting of the rows of $A$ 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 $T(m)$ of find_left_min, where $m$ is the number of rows? For the purpose of this discussion, let us focus on analyzing lm_recursion.

Let $A$ be an $m \times n$ array, so that num_rows == m and num_cols == n. If $m=1$, 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 $\Theta(n)$. We thus declare

As for the $m > 1$ case, we observe that lm_recursion consists of three steps:

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

Since $A$ is never modified throughout lm_recursion, there is no need to copy the data of $A$ to construct evens, which becomes $A$ in the recursive step. The construction of even thus reduces to collecting pointers to the even rows, which can be done in $\Theta(m/2)$ time.

The recursion step is invoked on evens, an array of $m/2$ rows. Since the recursion step is invoked precisely once without any additional procedure, it takes $T(m/2)$ time to run.

Finally, we have shown in 4-6d that the computation of mins takes $\Theta(m+n)$ time. It follows that the running time of lm_recursion is

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

Since

for all choices of $I$, we see that

We have shown above that $T(1) = \Theta(m)$, and so

Let us now prove the above estimate by induction. To this end, we fix $n$ and choose constants $k,K > 0$ such that

for all choices of $m$.

Let us first establish the upper bound

Fix $m \geq 2$ and assume inductively that

for all $% $, where $C,D > 0$ are constants to be chosen.

Observe that

So long as

we have

The above condition is satisfied precisely when

To establish the base case $m = 1$, we only need the hypothesis

We thus choose

so that $(\ast\ast)$ is trivially established, and that

thereby establishing $(\ast)$. It now follows from induction that

It remains to establish the lower bound

We fix $m \geq 2$ and assume inductively that

for all $% $, where $C,D > 0$ 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 $m = 1$, we only need the hypothesis

We therefore choose

so that $(\star)$ and $(\star\star)$ follow. We now conclude by induction that

which, along with the upper bound established above, implies

as was to be shown. $\square$

## 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 $f$. The solution is given by the formula

where $p$ is the unique real number that satisfies the identity

For the above example, we have $p = 1$, 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.” $\square$

### 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 $a_0,a_1,\ldots,a_k,\ldots$, 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 $z^n$ ($z^n/n!$ for exponential generating functions), summing on $n$, 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 $a_0 = 0$, $a_1 = 1$, $a_2 = 1$. We multiply both sides by $z^n$, sum over $n \geq 3$, and reindex the sums to obtain the identity

For notational simplicity, we let

the ordinary generating function of $(a_{n})_{n}$. Observe that

We can use the above computation to simplify $(\ast)$ as follows:

Using the initial condition $a_0 = 0$, $a_1 = 1$, $a_2 = 1$, we conclude that

Taking the partial fraction decomposition, we obtain

We now recall that

from which we conclude that

It follows that

for all $n \geq 0$.

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