4. Divide-and-Conquer

Exercises

4.1-1

Available in the latest revision of the IM.

4.1-2

Available in the latest revision of the IM.

4.1-3

Available in the latest revision of the IM.

4.1-4

Assume that $n$ is an exact power of 2, otherwise employ the "trick" from Exercise 4.1-1. The pseudocode calculates $C=C+A+B$ by recursively finding the following sums:

$$\begin{align*} C_{11} &= C_{11}+A_{11}+B_{11} \\ C_{12} &= C_{12}+A_{12}+B_{12}\\ C_{21} &= C_{21}+A_{21}+B_{21}\\ C_{22} &= C_{22}+A_{22}+B_{22} \end{align*}$$

Matrix-Add-Recursive(A, B, C, n)
1   if n == 1
2       // Base case.
3       c11 = c11 + a11 + b11
4       return
5   // Divide.
6       partition A, B, and C into n/2 x n/2 submatrices
        A11, A12, A21, A22; B11, B12, B21, B22;
        and C11, C12, C21, C22; respectively
7   // Conquer.
8   Matrix-Add-Recursive(A11, B11, C11, n/2)
9   Matrix-Add-Recursive(A12, B12, C12, n/2)
10  Matrix-Add-Recursive(A21, B21, C21, n/2)
11  Matrix-Add-Recursive(A22, B22, C22, n/2)

The recurrence is $T(n)=4T(n/2)+\Theta(1)$, so $T(n)=\Theta(n^2)$ (case 1 of the master theorem).

If we copy submatrices instead of performing index calculations, then the recurrence changes into $T(n)=4T(n/2)+\Theta(n^2)$, thus $T(n)=\Theta(n^2\lg n)$ (case 2 of the master theorem).

4.2-1

Available in the latest revision of the IM.

4.2-2

Available in the latest revision of the IM.

4.2-3

Available in the latest revision of the IM.

4.2-4

Available in the latest revision of the IM.

4.2-5

Available in the latest revision of the IM.

An alternative solution is presented below, using the same total number of operations as the approach shown in the IM. The primary advantage of this method is that it avoids the need to construct a potentially large product $(a+b)(c+d)$.

$$\begin{align*} p_1&=a(c+d)\space\space\space(=ac+ad) \\ p_2&=b(c−d)\space\space\space(=bc−bd) \\ p_3&=d(a+b)\space\space\space(=ad+bd) \\ \bold{re}&=p_1−p_3\space\space\space(=ac+ad−ad−bd=ac−bd) \\ \bold{im}&=p_2+p_3\space\space\space(=bc−bd+ad+bd=ad+bc) \end{align*}$$

4.2-6

Available in the latest revision of the IM.

4.3-1

Available in the latest revision of the IM.

4.3-2

Available in the latest revision of the IM.

4.3-3

Available in the latest revision of the IM.

4.4-1

Available in the latest revision of the IM.

4.4-2

Available in the latest revision of the IM.

4.4-3

Available in the latest revision of the IM.

4.4-4 🌟

Justifies the guess $T(n)=\Theta(n \lg n)$ as the solution to the recurrence $T(n) = T(αn)+T((1–α)n)+Θ(n)$, where α is a constant in the range 0 < α < 1.

Available in the latest revision of the IM.

4.5-1

Available in the latest revision of the IM.

4.5-2

Available in the latest revision of the IM.

4.5-3

Available in the latest revision of the IM.

4.5-4

Available in the latest revision of the IM.

4.5-5

Available in the latest revision of the IM.

4.6-1

$$\begin{align*} \sum_{j=0}^{\lfloor\log_bn\rfloor}(\log_bn-j)^k &\ge \sum_{j=0}^{\lfloor\log_bn\rfloor}(\lfloor\log_bn\rfloor-j)^k \\ &= \sum_{j=0}^{\lfloor\log_bn\rfloor}j^k && \text{(reindexing)} \\ &= \Omega(\lfloor\log_bn\rfloor^{k+1}) && \text{(by Exercise A.1-5)} \\ &= \Omega(\log_b^{k+1}n) && \text{(by Exercise 3.3-3)}. \end{align*}$$

★ 4.6-2

Performing $j=\lfloor\log_b(n/n_0)\rfloor$ iterations of the inequality $af(n/b) \le cf(n)$ yields $a^jf(n/b^j) \le c^jf(n)$. Notice that $n/b^j\ge n_0$ and $n/b^{j+1} < n_0$, so $n/b^j \in [n_0,bn_0)$. We have

$$f(n) \ge (a/c)^{\lfloor\log_b(n/n_0)\rfloor}f\bigl(n/b^{\lfloor\log_b(n/n_0)\rfloor}\bigr).$$

Let $\mu=\underset{[n_0,bn_0)}\inf f$, which can be regarded as a positive constant in the context of algorithmic analysis. We have two cases depending on the ratio $(a/c)$ that comprises the base of an exponential in the formula above.

(a/c) < 1

$$\begin{align*} f(n) &\ge (a/c)^{\lfloor\log_b(n/n_0)\rfloor}f\bigl(n/b^{\lfloor\log_b(n/n_0)\rfloor}\bigr) \\ &\ge (a/c)^{\log_b(n/n_0)}\mu \\ &= \frac{(n/n_0)^{\log_ba}}{(n/n_0)^{\log_bc}}\,\mu && \text{(by equations (3.18), (3.20), and (3.21))} \\[1mm] &= n^{\log_ba-\log_bc}\cdot n_0^{\log_bc-\log_ba}\cdot\mu \\ &= d \cdot n^{\log_ba-\log_bc} && \text{(} d=n_0^{\log_bc-\log_ba}\cdot\mu>0 \text{)} . \end{align*}$$

(a/c) ≥ 1

Since $\log_bc<0$, let $\epsilon=-\log_bc>0$. We get $f(n) \ge d \cdot n^{\log_ba+\epsilon}=\Omega(n^{\log_ba+\epsilon})$.

★ 4.6-3

In principle, the statement can be included into Lemma 4.3 as an extension to case 2. Of course, we must tolerate some lack of rigor, as $f(n)$ is not defined for $n=1$, which is assumed to be true in Lemma 4.3. Since $f(n)=\Theta(n^{\log_ba}/\lg n)$ we have that $f(n/b^j)=\Theta((n/b^j)^{\log_ba}/\lg(n/b^j))$. Notice that $n/b^j=1$ when $\log_bn$ is an integer, so we will sum up to $\lfloor\log_bn\rfloor-1$ to avoid potential division by zero error. The rest of the steps are rather mechanical.

$$\begin{align*} g(n) &= \sum_{j=0}^{\lfloor\log_bn\rfloor-1}a^j\Theta\left(\left(\frac{n}{b^j}\right)^{\log_ba}\!\!\Bigm/\lg\left(\frac{n}{b^j}\right)\right) \\ &= \Theta\left(\sum_{j=0}^{\lfloor\log_bn\rfloor-1}a^j\left(\frac{n}{b^j}\right)^{\log_ba}\!\!\Bigm/\lg\left(\frac{n}{b^j}\right)\right) && \text{(by Exercise A.1-1)} \\ &= \Theta\left(n^{\log_ba}\sum_{j=0}^{\lfloor\log_bn\rfloor-1}\frac{a^j}{b^{j\log_ba}\lg(n/b^j)}\right) \\ &= \Theta\left(n^{\log_ba}\sum_{j=0}^{\lfloor\log_bn\rfloor-1}\frac{1}{\lg(n/b^j)}\right) && \text{(by equation (3.21))} \\ &= \Theta\left(n^{\log_ba}\sum_{j=0}^{\lfloor\log_bn\rfloor-1}\frac{\log_b2}{\log_b(n/b^j)}\right) && \text{(by equation (3.19))} \\ &= \Theta\left(n^{\log_ba}\log_b2\sum_{j=0}^{\lfloor\log_bn\rfloor-1}\frac{1}{\log_bn-j}\right) && \text{(by equations (3.18) and (3.20))} \\ &= \Theta\left(n^{\log_ba}\sum_{j=0}^{\lfloor\log_bn\rfloor-1}\frac{1}{\log_bn-j}\right) && \text{($\log_b2>0$ is a constant)}. \end{align*}$$

The summation within the $\Theta$-notation can be bounded from above as follows:

$$\begin{align*} \sum_{j=0}^{\lfloor\log_bn\rfloor-1}\frac{1}{\log_bn-j} &\le \sum_{j=0}^{\lfloor\log_bn\rfloor-1}\frac{1}{\lfloor\log_bn\rfloor-j} \\ &= \sum_{j=1}^{\lfloor\log_bn\rfloor}\frac{1}{j} && \text{(reindexing)} \\ &= \ln(\lfloor\log_bn\rfloor)+O(1) && \text{(by equation (A.9))} \\ &= O(\lg\lg n). \end{align*}$$

The corresponding lower bound is

$$\begin{align*} \sum_{j=0}^{\lfloor\log_bn\rfloor-1}\frac{1}{\log_bn-j} &\ge \sum_{j=0}^{\lfloor\log_bn\rfloor-1}\frac{1}{\lfloor\log_bn\rfloor+1-j} \\ &= \sum_{j=2}^{\lfloor\log_bn\rfloor+1}\frac{1}{j} && \text{(reindexing)} \\ &> \sum_{j=1}^{\lfloor\log_bn\rfloor}\frac{1}{j} -1 \\ &= \ln(\lfloor\log_bn\rfloor)+O(1)-1 && \text{(by equation (A.9))} \\ &= \Omega(\lg\lg n). \end{align*}$$

Theorem 3.1 implies that $g(n)=\Theta(n^{\log_ba}\lg\lg n)$. Following the outline of the proof of Theorem 4.4 for case 2 from the book, we have

$$\begin{align*} f'(n) &= f(n_0n) \\ &= \Theta((n_0n)^{\log_ba}/\lg(n_0n)) \\ &= \Theta(n^{\log_ba}/\lg n) \quad \checkmark \\ \hline \\ T(n) &= T'(n/n_0) \\ &= \Theta((n/n_0)^{\log_ba})+\Theta((n/n_0)^{\log_ba}\lg\lg(n/n_0)) \\ &= \Theta(n^{\log_ba})+\Theta(n^{\log_ba}\lg\lg n) \\ &= \Theta(n^{\log_ba}\lg\lg n) && \text{(by Problem3-5(c))}. \end{align*}$$

★ 4.7-1 🌟

Shows that we can drop the asymptotics on a driving function in any Akra-Bazzi recurrence without affecting its asymptotic solution.

Let the initial conditions be $T'(n)=cT(n)$ for $0<n<n_0$, where $n_0>0$ is the corresponding threshold value. This is possible, since the implicit initial conditions of $T(n)$ are given. We now prove by induction on $n$ that we can maintain the relationship $T'(n)=cT(n)$ for all $n>0$.

For $0<n<n_0$ (base case) the equality holds by design. For the inductive step, assume that $n \ge n_0$

$$\begin{align*} T'(n) &= cf(n)+\sum_{i=1}^k\ a_iT'(n/b_i)\\ &= cf(n)+\sum_{i=1}^k a_icT(n/b_i) && \text{(by the inductive hypothesis)} \\ &= c\bigg(f(n)+\sum_{i=1}^k a_iT(n/b_i)\bigg) \\ &= cT(n). \end{align*}$$

Choosing the initial conditions such that $T'(n)=cT(n)$ for $0<n<n_0$, the recurrence implies $T'(n)=cT(n)$ for all $n \ge n_0$. Therefore, $T'(n)=cT(n)$ for all $n>0$.

If $T(n)$ has $\Theta(g(n))$ as a solution, then the solution of $T'(n)$ is $c \cdot \Theta(g(n))=\Theta(g(n))$. Thus, scaling the driving function by a constant factor does not alter the asymptotic growth of the solution in the Akra-Bazzi recurrence.

4.7-2

Choose $d=\phi^2+1>1$, such that

$$\begin{align*} \bold{f(n)/d} &= n^2/(\phi^2+1) \\ &\le n^2 \\ &\le \bold{\psi^2n^2} && \text{($\psi \ge 1$)} \\ &\le (\phi^2+1)n^2 && \text{($\psi \le \phi$)} \\ &= \bold{df(n)}. \end{align*}$$

This proves that $f(n)=n^2$ satisfies the polynomial-growth condition.

Select any $\phi>1$, so that for $\psi=2$ we have

$$\begin{align*} f(\psi n) &= 2^{\psi n} \\ &= 2^{2n} \\ &= 2^n\cdot2^n \\ &\nleq d2^n && \text{(for any constant $d$)}. \end{align*}$$

This proves that $f(n)=2^n$ does not satisfy the polynomial-growth condition.

4.7-3

Let $n_0=\hat n>0$ to reconcile an inconsistency, at the time of writing this text, between the problem statement and the definition of the polynomial-growth condition from the book.

A trivial nonnegative function $f(n)=0$ for all $n \ge n_0$ satisfies the polynomial-growth condition, but it cannot represent the driving function in any realistic scenario. So, assume that $f(n)$ denotes a proper cost function in equation (4.22).

Suppose, for the sake of contradiction, that there exists some $n \ge n_0$ where $f(n)=0$. Then, for any $\psi \in[1,\phi]$ the polynomial-growth inequality becomes $0 \le f(\psi n) \le 0$, which implies $f(\psi n)=0$. Since $\phi$ can be chosen arbitrarily large, this means that $f(n)$ must be identically zero on $[n_0, \infin)$. But this contradicts our initial assumption that $f(n)$ is nontrivial above some threshold. Therefore, $f(n)$ must be positive for all sufficiently large $n$.

★ 4.7-4

Read my post on StackExchange for Mathematics. It also provides an example of a polynomially bounded function that does not satisfy the PGC.

4.7-5

To solve math problems, you can use a tool such as WolframAlpha. Each subproblem includes executable commands for WolframAlpha along with their corresponding responses, which are substituted into equation (4.23).

a.

solve 1/2^p + 1/3^p + 1/6^p = 1 for real p

We get that $p=1$. We can now calculate the required definite integral.

Integrate[x Log[2,x]/x^2,{x,1,n}]

The result is $\cfrac{\ln^2 n}{\ln 4}$, hence $T(n)=\Theta(n\lg^2 n)$.

b.

solve 3/3^p + 8/4^p = 1 for real p

We get that $p \approx 1.86<2$. Notice that the integral becomes $I(n)=\int_1^n \frac{x^{1-p}}{\lg x}dx$, so it does not converge due to division by zero. This is a fine example, that you may run into technical difficulties in leveraging the Akra-Bazzi method. At any rate, the Akra-Bazzi theorem states that the lower limit of integration (which defaults to 1) can be replaced by any sufficiently large constant $c$ without affecting the asymptotic solution. This is because:

$$\int_1^n = \int_1^c + \int_c^n = O(1) + \int_c^n \implies I(n) = \int_2^n \frac{x^{1-p}}{\lg x} dx \quad \text{ for $c=2$}.$$

You can calculate the integral using the following Sage code:

var('x p n')
assume(p > 1, p < 2)
assume(n > 2)

integrand = (x^(1-p)) / (log(x) / log(2))
result = integrate(integrand, x, 2, n)
show(result)

The output is

$$\displaystyle -{\rm Ei}\left(-{\left(p - 2\right)} \log\left(2\right)\right) \log\left(2\right) + {\rm Ei}\left(-{\left(p - 2\right)} \log\left(n\right)\right) \log\left(2\right)=\Theta({\rm Ei}\left({\left(2-p\right)} \ln n\right)).$$

The $E_i$ is the exponential integral function, thus

$$\text{Ei}((2-p)\ln n) \sim \frac{e^{(2-p)\ln n}}{(2-p)\ln n} = \frac{n^{2-p}}{(2-p)\ln n}=\Theta\left(\frac{n^{2-p}}{\lg n}\right).$$

This gives $T(n) = \Theta(n^2/\lg n)$.

Escaping the vagaries of calculus is perhaps a better path. In this case, we may immediately decipher the lower bound based on the driving function, and simply use it as a candidate for an upper bound. The latter can be easily proven using the substitution method.

c.

Evidently $p=0$, since $a_1+a_2=1$. Issuing Integrate[Log[2,x]/x,{x,1,n}], we get $T(n)=\Theta(\lg^2 n)$.

d.

We can immediately see that $p=-1$. The definite integral is $\ln n$. Thus, $T(n)=\Theta(\lg n/n)$.

e.

solve 3/3^p + 3/(3/2)^p = 1 for real p

We get that $p=3$. The definite integral is $-1/n$. Thus, $T(n)=\Theta(n^3)$.

★ 4.7-6

The master method is a special case of the Akra-Bazzi framework, where $k=1$, $a_1=a$, and $b_1=b$. Therefore, $a/b^p=1 \implies p=\lg_b a$. Also, let $n_0\ge1$ such that for all $n \ge n_0$ a driving function is defined and nonnegative. Notice that the integral $I_0 = \int_1^{n_0}\frac{f(x)}{x^{p+1}}\,dx$ is some nonnegative value, due to $f(n)$ being nonnegative. We use this fact in all subproblems.

Case 1

Suppose $f(n)=O(n^{p-\epsilon})$ for some constant $\epsilon>0$, so $0 \le f(n)\le cn^{p-\epsilon}$.

The upper bound is

$$\begin{align*} I &= I_0+\int_{n_0}^n\frac{f(x)}{x^{p+1}}\,dx \\[1mm] &\le I_0+\int_{n_0}^n\frac{cx^{p-\epsilon}}{x^{p+1}}\,dx \\[1mm] &= I_0+c\int_{n_0}^nx^{-\epsilon-1}\,dx \\[1mm] &= I_0+c\left[\frac{x^{-\epsilon}}{-\epsilon}\right]_{n_0}^n \\[1mm] &= I_0+(c/\epsilon)(n_0^{-\epsilon}-n^{-\epsilon}) \\ &< I_0+(c/\epsilon)n_0^{-\epsilon} \\ &= O(1). \end{align*}$$

Since the integral $I$ is always positive, if we exclude an identically zero driving function from the picture, we get that $I=\Theta(1)$. By equation (4.23), we get that $T(n)=\Theta(n^p(1+I))=\Theta(n^p)=\Theta(n^{\log_ba})$.

Case 2

Suppose $f(n)=\Theta(n^p\lg^kn)$ for some constant $k\ge 0$, so $0 \le c_1n^p\lg^kn\le f(n)\le c_2n^p\lg^kn$.

We first need to solve the indefinite integral $\int\frac{\lg^kx}{x}\,dx$, for example, by using WolframAlpha.

Integrate[Log[2,x]^k/x,x]

We get that it equals $\cfrac{ \ln^{k+1} n}{(\ln 2)^k (k+1)}+C=\cfrac{(\ln2)\lg^{k+1}x}{k+1}+C$.

The lower bound is

$$\begin{align*} I &= I_0+\int_{n_0}^n\frac{f(x)}{x^{p+1}}\,dx \\[1mm] &\ge \int_{n_0}^n\frac{c_1x^p\lg^kx}{x^{p+1}}\,dx \\[1mm] &= c_1\int_{n_0}^n\frac{\lg^kx}{x}\,dx \\[1mm] &= c_1\left[\frac{(\ln2)\lg^{k+1}x}{k+1}\right]_{n_0}^n \\[1mm] &= \frac{c_1(\ln2)}{k+1}\cdot(\lg^{k+1}n-\lg^{k+1}n_0) \\[1mm] &= \Omega(\lg^{k+1}n). \end{align*}$$

The upper bound is

$$\begin{align*} I &= I_0+\int_{n_0}^n\frac{f(x)}{x^{p+1}}\,dx \\[1mm] &\le I_0+\int_{n_0}^n\frac{c_2x^p\lg^kx}{x^{p+1}}\,dx \\[1mm] &= I_0+c_2\int_{n_0}^n\frac{\lg^kx}{x}\,dx \\[1mm] &= I_0+c_2\left[\frac{(\ln2)\lg^{k+1}x}{k+1}\right]_{n_0}^n \\[1mm] &= I_0+\frac{c_2(\ln2)}{k+1}\cdot(\lg^{k+1}n-\lg^{k+1}n_0) \\[1mm] &= O(\lg^{k+1}n). \end{align*}$$

Theorem 3.1 implies that $I=\Theta(\lg^{k+1}n)$. Finally, we have

$$\begin{align*} T(n) &= \Theta(n^p(1+I)) \\ &= \Theta(n^p(1+\Theta(\lg^{k+1}n))) \\ &= \Theta(n^p\lg^{k+1}n) \\ &= \Theta(n^{\log_ba}\lg^{k+1}n). \end{align*}$$

Case 3

Read my post on StackExchange for Mathematics.

Problems

4-1 Recurrence examples

Available in the latest revision of the IM.

4-2 Parameter-passing costs

a.

• $T_{a1}(N,n) = T_{a1}(N,n/2)+\Theta(1)$ resolves to $T_{a1}(N,n)=\Theta(1)\cdot\Theta(\lg n)=\Theta(\lg n)$ (see Exercise 4.5-3).

• $T_{a2}(N,n) = T_{a2}(N,n/2)+\Theta(N)$ resolves to $T_{a2}(N,n)=\Theta(N)\cdot\Theta(\lg n)=\Theta(N\lg n)$.

• $T_{a3}(N,n) = T_{a3}(N,n/2)+\Theta(n)$ resolves to $T_{a3}(N,n)=\Theta(n)$ according to case 3 of the master theorem.

b.

• $T_{b1}(N,n) = 2T_{b1}(N,n/2)+\Theta(n)$ resolves to $T_{b1}(N,n)=\Theta(n\lg n)$.

• $T_{b2}(N,n) = 2T_{b2}(N,n/2)+\Theta(n+N)$ resolves to $T_{b2}(N,n)=\Theta(n(\lg n+N))=\Theta(nN)$. Recall that $N \ge n$. We have to be careful with that extra $\Theta(N)$ term, since it is a cost that occurs at each recursive call; we have a branching factor of 2, therefore, we perform array copying $2^{\lg n}=n$ times. This is fundamentally different situation than with a binary search from the previous subproblem.

• $T_{b3}(N,n) = 2T_{b3}(N,n/2)+\Theta(n)$ resolves to $T_{b3}(N,n)=\Theta(n\lg n)$.

c.

• $T_{c1}(N,n) = 8T_{c1}(N,n/2)+\Theta(1)$ resolves to $T_{c1}(N,n)=\Theta(n^3)$.

• $T_{c2}(N,n) = 8T_{c2}(N,n/2)+\Theta(N^2)$ resolves to $T_{c2}(N,n) = \Theta(n^3N^2)$ (see the comment in part (b)).

• $T_{c3}(N,n) = 8T_{c3}(N,n/2)+\Theta(n^2)$ resolves to $T_{c3}(N,n)=\Theta(n^3)$ (see Exercise 4.1-3).

4-3 Solving recurrences with a change of variables

Available in the latest revision of the IM.

4-4 More recurrence examples

Available in the latest revision of the IM.

The solutions in the latest IM are based on the previous edition of the book. Despite being correct, they could be solved more efficiently using the newly added chapters 4.6 and 4.7.

Parts (b) and (e) are belonging to the extended case 2 of the master theorem (see Exercise 4.6-3).

Part (d) is covered by the Akra-Bazzi method. Based on Exercise 4.6-1, we can ignore the scaling factor of ½ on a driving function and take that $f(n)=n$. It trivially satisfies the polynomial-growth condition. Furthermore, the perturbation factor $h_i(n)=-2$ surely satisfies $|h_i(n)|=2=O(n/\lg^{1+\epsilon})$ for some constant $\epsilon>0$, so it can be also ignored. In this problem $p=1$, so the definite integral becomes trivial.

Part (f) is also easily solved using the Akra-Bazzi method with $0<p<1$ (actually $p \approx 0.88$).

Part (j) can be easily solved with a change of variables. Let $S(n)=T(n)/n=S(\sqrt n)+1$ and $m=\lg n$. In terms of $m$, we have $R(m)=R(m/2)+1$ that resolves to $R(m)=\Theta(\lg m)$. Thus, $S(n)=R(m)=\Theta(\lg {\lg n})$ and finally $T(n)=nS(n)=\Theta(n \lg \lg n)$.

4-5 Fibonacci numbers

Available in the latest revision of the IM.

4-6 Chip testing

Available in the latest revision of the IM.

4-7 Monge arrays

a.

The "only if" direction is trivial. Just substitute $k=i+1$ and $l=j+1$ into the main definition. You can find the proof of the "if" part here (lookup Lemma 1.1).

b.

We should ensure that $A[1,3] \in [24,29]$.

c.

Suppose for the sake of contradiction that there exists a row $1\le i<m$ such that $f(i)>f(i+1)$. We have $A[i,f(i+1)] > A[i,f(i)]$ and $A[i+1,f(i)] \ge A[i+1,f(i+1)]$ implying $A[i,f(i+1)]+A[i+1,f(i)] > A[i,f(i)]+A[i+1,f(i+1)]$. But this contradicts the definition of an array being Monge for coordinates $j=f(i+1)$, $k=i+1$, and $l=f(i)$.

d.

To calculate $f(i)$ for odd $i$ we use values of $f$ in neighboring rows. By part (c) we know that $f(i-1)\le f(i) \le f(i+1)$, so the index of a minimum element must be inside an interval $[f(i-1),f(i+1)]$. The size of this interval is $f(i+1)-f(i-1)+1$. The total number of comparisons is (assume $f(0)=1$ and $f(m+1)=n$)

$$\begin{align*} \sum_{\substack{1\le i\le m\\\text{$i$ is odd}}}(f(i+1)-f(i-1)+1) &= O(m)+(f(m)-f(0)) && \text{(telescoping sum)} \\[2mm] &= O(m)+O(n) \\ &= O(m+n). \end{align*}$$

e.

The algorithmic recurrence is $T(m,n)=T(\lfloor m/2\rfloor,n)+O(m+n)$ for $m >1$.

Let $c>0$ and $n_0>1$ represent the constants hidden by the O-notation. Assume $n \ge n_0$. We use the substitution method and induction on $m$ to prove that $T(m,n) \le c'(m+n \lg m)$ for some $c' > 0$.

We have

$$\begin{align*} T(m,n) &\le c'(\lfloor m/2\rfloor+n\lg(\lfloor m/2\rfloor))+c(m+n) \\ &\le c'(m/2+n\lg (m/2))+c(m+n) \\ &= c'(m+n\lg m)-c'(m/2+n)+c(m+n) \\ &\le c'(m+n\lg m). \end{align*}$$

when $-c'(m/2+n)+c(m+n) \le 0$, which is true if $c' \ge 2c$.