Divide and Conquer
Contents
Introduction
Divide-and-conquer
Problem-Solving Template
D&C problem-solving template
Recurrences
Method 1: Iteration and substitution
\[ \begin{align*} T(n) &= T \left(\frac{n}{2} \right) + 1\\ &= T \left(\frac{n}{2^2} \right) + 1 + 1\\ &= T \left(\frac{n}{2^3} \right) + 1 + 1 + 1\\ &= T \left(\frac{n}{2^k} \right) + \underbrace{1 + 1 + \cdots + 1}_{k \text{ times}}\\ &= T \left(\frac{n}{2^k} \right) + k \qquad \left( \text{set the basecase } \frac{n}{2^k} = 1 \right)\\ &= T(1) + \log n\\ &= 1 + \log n\\ &\in \Theta({\log n}) \end{align*} \]\[ \begin{aligned} T(n) &= 2 T \left(\frac{n}{3} \right) + \Theta({n})\\ T(n) &\le 2 T \left(\frac{n}{3} \right) + cn\\ &\le 2 \left( 2T \left(\frac{n}{3^2} \right) + \frac{cn}{3} \right) + cn\\ &= 2^2 T \left(\frac{n}{3^2}\right) + \frac{2}{3} cn + cn\\ &\le 2^2 \left( 2 T \left(\frac{n}{3^3}\right) + \frac{cn}{3^2} \right) + \frac{2}{3} cn + cn\\ &= 2^3 T \left(\frac{n}{3^3}\right) + \frac{2^2}{3^2} cn + \frac{2}{3} cn + cn\\ &= 2^3 T \left(\frac{n}{3^3}\right) + cn \left( 1 + \left( \frac{2}{3} \right) + \left( \frac{2}{3} \right)^2 \right)\\ &\le 2^k T \left(\frac{n}{3^k}\right) + cn \left( 1 + \left( \frac{2}{3} \right) + \left( \frac{2}{3} \right)^2 + \cdots + \left( \frac{2}{3} \right)^{k - 1} \right)\\ &\le 2^k T \left(\frac{n}{3^k}\right) + c' n \qquad (\text{geometrically decreasing series})\\ & \left(\text{Set basecase $\frac{n}{3^k} = 1$. This implies $3^k = n$ and $2^k = n^{\log_3 2}.$}\right)\\ &= n^{\log_3 2} \cdot T(1) + c' n\\ &\le c'' n\\ &\in \mathcal{O}({n}) \end{aligned} \]
Method 2: Recursion tree
- $T(n) = 2 T \left(\frac{n}{3} \right) + cn$
Method 3: Guess and test
- Given a recurrence, guess a function and test if the recurrence matches the function by induction.
- If the test fails, you might have to consider a fast-growing or slow-growing function and test it again.
- This is a pretty dangerous method because if a function does not match a recurrence, it does not necessarily imply that another one proportional to this one will not work.
Method 4: Master theorem
Suppose $T(n)$ has the following recurrence: \[ T(n) = \left. \begin{cases} c & \text{if } n < d,\\ aT\left(\frac{n}{b}\right) + f(n) & \text{if } n \ge d. \end{cases} \right\} \]
where $d \ge 1$ is a fixed natural number and $a \ge 1, c > 0, b > 1$ are real constants, and $f(n)$ is a positive function for $n \ge d$.
Then, the complexity of $T(n)$ is \[ T(n) \in \left. \begin{cases} \Theta(n^{\Delta}) & \text{if } f(n) \in \mathcal{O}(n^{\Delta - \epsilon}) \text{ for } \epsilon > 0,\\ \Theta(f(n) \log n) & \text{if } f(n) \in \Theta(n^{\Delta} \log^k n),\\ \Theta(f(n)) & \begin{array}{@{}l@{}} \text{if } f(n) \in \Omega(n^{\Delta + \epsilon}) \text{ for } \epsilon > 0 \text{ and } f(n) > af(n/b). \end{array}\\ \end{cases} \right\} \] where $\Delta = \log_b a$ is the discriminant of the recurrence.
Justification of master theorem
\[ \begin{aligned} T(n) &= a T \left( \frac{n}{b} \right) + f(n)\\ &= a^2 T \left( \frac{n}{b^2} \right) + af\left(\frac{n}{b}\right) + f(n)\\ &= a^3 T \left( \frac{n}{b^3} \right) + a^2f\left(\frac{n}{b^2}\right) + af\left(\frac{n}{b}\right) + f(n)\\ &= a^{\log_b n} T (1) + \sum_{i = 0}^{\log_b n - 1} a^i f\left(\frac{n}{b^i}\right)\\ &= n^{\log_b a} + \sum_{i = 0}^{\log_b n - 1} a^i f\left(\frac{n}{b^i}\right) \end{aligned} \]- $f(n)$ is polynomially smaller than $n^{\Delta}$ $\implies T(n) \in \Theta(n^{\Delta})$
- $f(n)$ is asymptotically close to $n^{\Delta}$ $\implies T(n) \in \Theta(f(n) \log n)$
- $f(n)$ is polynomially larger than $n^{\Delta}$ $\implies T(n) \in \Theta(f(n))$
Problems
Solve $T(n) = T(n/2) + 1$ using the master theorem
- $a = 1$
- $b = 2$
- $f(n) = 1 = n^0$
- $n^{\Delta} = n^{\log_b a} = n^{\log_2 1} = n^0$
-
As $f(n) \in \Theta(n^{\Delta} \log^k n)$, i.e., $n^0 \in \Theta(n^0
\log^0 n)$, we apply Case 2
$T(n) \in \Theta(f(n) \log n) = \Theta(n^0 \log n) = \Theta(\log n)$
Solve $T(n) = 2T(n/2) + 1$ using the master theorem
- $a = 2$
- $b = 2$
- $f(n) = 1 = n^0$
- $n^{\Delta} = n^{\log_b a} = n^{\log_2 2} = n^1$
-
As $f(n) \in \mathcal{O}(n^{\Delta - \epsilon})$, i.e., $n^0 \in
\mathcal{O}(n^{1 - 1})$, we apply Case 1
$T(n) \in \Theta(n^{\Delta}) = \Theta(n)$
Solve $T(n) = 2T(n/2) + n$ using the master theorem
- $a = 2$
- $b = 2$
- $f(n) = n = n^1$
- $n^{\Delta} = n^{\log_b a} = n^{\log_2 2} = n^1$
-
As $f(n) \in \Theta(n^{\Delta} \log^k n)$, i.e., $n^1 \in \Theta(n^1
\log^0 n)$, we apply Case 2
$T(n) \in \Theta(f(n) \log n) = \Theta(n \log n)$
Solve $T(n) = 2T(n/2) + n^2$ using the master theorem
- $a = 2$
- $b = 2$
- $f(n) = n^2$
- $n^{\Delta} = n^{\log_b a} = n^{\log_2 2} = n^1$
-
As $f(n) \in \Omega(n^{\Delta + \epsilon})$, i.e., $n^2 \in
\Omega(n^{1 + 1})$, we apply Case 3
$T(n) \in \Theta(f(n)) = \Theta(n^2)$
Solve the following recurrences using the master theorem
-
$T(n) = T(\sqrt{n}) + n$
Master theorem cannot be directly applied
Reason: $\sqrt{n}$ cannot be written as $n/b$ for any real constant $b > 1$ -
$T(n) = n T(n/2) + n$
Master theorem cannot be directly applied
Reason: $a = n$ is not a constant -
$T(n) = T(n-1) + n$
Master theorem cannot be directly applied
Reason: Subproblem $(n-1)$ cannot be written as $n/b$ for any real constant $b > 1$ -
$T(n) = T(n/2) + T(n/3) + n$
Master theorem cannot be directly applied
Reason: Cannot have multiple subproblems of different sizes -
$T(n) = 2 T(n/(2/3)) + 2^n$
Master theorem cannot be directly applied
Reason: $b < 1$; $b$ should have been larger than $1$ -
$T(n) = 2 T(n/2) + n \times (1 + \sin n)$
Master theorem cannot be directly applied
Reason: $f(n)$ does not have a clean $\Theta$-class relative to $n^{\Delta}$ -
$T(n) = T(n/2) + T(n/2) + T(n/2) - n$
Master theorem cannot be directly applied
Reason: $f(n)$ is a negative function -
$T(n) = 2 T(n/2) + g(n)$ where $g(n)$ is $n$ if $n$ even, $1$ if $n$
odd
Master theorem cannot be directly applied
Reason: $g(n)$ does not have a clean $\Theta$-class relative to $n^{\Delta}$
Problems and Solutions
Array Sum
Problem
Compute the sum of elements of a given array.
Step 1. Subproblem
\[ \begin{aligned} &\mathrm{Sum}(A[\ell \ldots h]) = \text{Sum of all elements in subarray } A[\ell \ldots h]\\ &\text{Compute } \mathrm{Sum}(A[1 \ldots n]) \end{aligned} \]Step 2. Recursive formulation
Step 3. Algorithm
\begin{algorithm}
\begin{algorithmic}
\FUNCTION{ArraySum}{$A[low \ldots high]$}
\IF{$low > high$}
\RETURN $0$
\ENDIF
\IF{$low = high$}
\RETURN $A[low]$
\ENDIF
\STATE $mid \gets \lfloor (low + high)/2 \rfloor$
\STATE
$leftsum \gets$
\CALL{ArraySum}{$A[low \ldots mid]$}
\STATE
$rightsum \gets$
\CALL{ArraySum}{$A[(mid+1) \ldots high]$}
\RETURN $(leftsum + rightsum)$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Step 4. Example
Step 5. Complexity
\[ \begin{aligned} &\text{Time } T(n) = \left. \begin{cases} \Theta(1) & \text{if } n = 1,\\ 2T(n/2) + \Theta(1) & \text{if } n > 1. \end{cases} \right\} \in \Theta(n) \\ &\text{Space } S(n) = \left. \begin{cases} \Theta(1) & \text{if } n = 1,\\ S(n/2) + \Theta(1) & \text{if } n > 1. \end{cases} \right\} \in \Theta(\log n) \end{aligned} \]Integer Multiplication
Problem
Multiply two $n$-bit nonnegative binary numbers.
For simplicity, we assume $n$ is a power of 2.
Formally, let $A[1 \ldots n]$ and $B[1 \ldots n]$ be $n$-bit binary numbers. Compute $C = C[1 \ldots (2n)]$ such that \[ C[1 \ldots (2n)] = A[1 \ldots n] \times B[1 \ldots n] \]
For simplicity, we assume $n$ is a power of 2.
Formally, let $A[1 \ldots n]$ and $B[1 \ldots n]$ be $n$-bit binary numbers. Compute $C = C[1 \ldots (2n)]$ such that \[ C[1 \ldots (2n)] = A[1 \ldots n] \times B[1 \ldots n] \]
Step 1. Subproblem
\[ \begin{aligned} &\mathrm{Product}(A[1 \ldots n], B[1 \ldots n]) = \text{Multiply two nonnegative numbers $A[1 \ldots n]$ and $B[1 \ldots n]$.}\\ &\text{Compute } \mathrm{Product}(A[1 \ldots n], B[1 \ldots n]) \end{aligned} \]Step 2. Recursive formulation
\[ \begin{aligned} A \times B &= (A_L A_R) \times (B_L B_R)\\ &= (A_L \cdot 2^{n / 2} + A_R) \times (B_L \cdot 2^{n / 2} + B_R)\\ &= (A_L \times B_L) \cdot 2^n + (A_L \times B_R + A_R \times B_L)\cdot 2^{n/2} + (A_R \times B_R) \end{aligned} \]
Step 3. Algorithm
\begin{algorithm}
\begin{algorithmic}
\INPUT
Two $n$-bit nonnegative binary numbers $A$ and $B$, where $n$ is a power of 2
\OUTPUT
Product of nonnegative integers
$A$ and $B$
\FUNCTION{Product}{$A[1 \ldots n], B[1 \ldots n]$}
\IF{$n = 1$}
\RETURN $A[n] \times B[n]$
\ENDIF
\STATE $m \gets n/2$
\STATE
Let $A_L \gets A[1 \ldots m]$, $A_R \gets A[(m + 1) \ldots n]$
\STATE
Let $B_L \gets B[1 \ldots m]$, $B_R \gets B[(m + 1) \ldots n]$
\STATE
$P_1 \gets$ \CALL{Product}{$A_L, B_L$}
\STATE
$P_2 \gets$ \CALL{Product}{$A_L, B_R$}
\STATE
$P_3 \gets$ \CALL{Product}{$A_R, B_L$}
\STATE
$P_4 \gets$ \CALL{Product}{$A_R, B_R$}
\STATE $result \gets (P_1 \cdot 2^n
+ (P_2 + P_3)\cdot 2^{n/2}
+ P_4)$
\RETURN $result$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}
Step 4. Example
\[ \begin{aligned} 1100 \times 1001 &= (11)(00) \times (10)(01)\\ &= (11 \cdot 2^2 + 00) \times (10 \cdot 2^2 + 01)\\ &= (11 \times 10)\cdot 2^4 + (11 \times 01 + 00 \times 10)\cdot 2^2 + (00 \times 01) \end{aligned} \]Step 5. Complexity
\[ \begin{aligned} &\text{Time } T(n) = \left. \begin{cases} \Theta(1) & \text{if } n = 1,\\ 4T(n/2) + \Theta(n) & \text{if } n > 1. \end{cases} \right\} \in \Theta(n^2) \\ &\text{Space } S(n) = \left. \begin{cases} \Theta(1) & \text{if } n = 1,\\ S(n/2) + \Theta(n) & \text{if } n > 1. \end{cases} \right\} \in \Theta(\log n) \end{aligned} \]Amazing idea
Problem
Is there is a strategy to perform multiplication of two complex numbers with only 3 multiplications?
$(a + ib)(c + id) = (ac-bd) + i(bc+ad)$
Is there is a strategy to perform multiplication of two complex numbers with only 3 multiplications?
$(a + ib)(c + id) = (ac-bd) + i(bc+ad)$
Solution 1
Let $x = bd$, $y = ac$, and $z = (a + b)(c + d)$.
Then, real part $= y - x$ and imaginary part $= z - x - y$.
Solution 2
Let $x = c(a + b)$, $y = a(d-c)$, and $z = b(c+d)$.
Then, real part $= x - z$ and imaginary part $= x + y$.
Solution 3
Let $x = c(a + b)$, $y = a(c-d)$, and $z = d(a - b)$.
Then, real part $= y + z$ and imaginary part $= x - y$.
Let $x = bd$, $y = ac$, and $z = (a + b)(c + d)$.
Then, real part $= y - x$ and imaginary part $= z - x - y$.
Solution 2
Let $x = c(a + b)$, $y = a(d-c)$, and $z = b(c+d)$.
Then, real part $= x - z$ and imaginary part $= x + y$.
Solution 3
Let $x = c(a + b)$, $y = a(c-d)$, and $z = d(a - b)$.
Then, real part $= y + z$ and imaginary part $= x - y$.
Step 1. Subproblem
\[ \begin{aligned} &\mathrm{Product}(A[1 \ldots n], B[1 \ldots n]) = \text{Multiply two nonnegative numbers $A[1 \ldots n]$ and $B[1 \ldots n]$.}\\ &\text{Compute } \mathrm{Product}(A[1 \ldots n], B[1 \ldots n]) \end{aligned} \]Step 2. Recursive formulation
\[ \begin{aligned} A \times B &= (A_L A_R) \times (B_L B_R)\\ &= (A_L \cdot 2^{n / 2} + A_R) \times (B_L \cdot 2^{n / 2} + B_R)\\ &= (A_L \times B_L)\cdot 2^n + (A_L \times B_R + A_R \times B_L)\cdot 2^{n/2}\\ &\qquad + (A_R \times B_R)\\ &= (A_L \times B_L)\cdot 2^n\\ &\qquad + \left( \begin{array}{c} (A_L + A_R)\times(B_L + B_R)\\ - (A_L \times B_L) - (A_R \times B_R) \end{array} \right)\cdot 2^{n/2}\\ &\qquad + (A_R \times B_R) \end{aligned} \]
Step 3. Algorithm
\begin{algorithm}
\begin{algorithmic}
\INPUT
Two $n$-bit nonnegative binary numbers $A$ and $B$, where $n$ is a power of 2
\OUTPUT
Product of nonnegative integers
$A$ and $B$
\FUNCTION{Product}{$A[1 \ldots n], B[1 \ldots n]$}
\IF{$n = 1$}
\RETURN $A[n] \times B[n]$
\ENDIF
\STATE $m \gets n/2$
\STATE
Let $A_L \gets A[1 \ldots m]$, $A_R \gets A[(m + 1) \ldots n]$
\STATE
Let $B_L \gets B[1 \ldots m]$, $B_R \gets B[(m + 1) \ldots n]$
\STATE
$P_1 \gets$ \CALL{Product}{$A_L, B_L$}
\STATE
$P_2 \gets$ \CALL{Product}{$(A_L + A_R), (B_L + B_R)$}
\STATE
$P_3 \gets$ \CALL{Product}{$A_R, B_R$}
\STATE $result \gets (P_1 \cdot 2^n
+ (P_2 - P_1 - P_3)\cdot 2^{n/2}
+ P_3)$
\RETURN $result$
\ENDFUNCTION
\end{algorithmic}
\end{algorithm}