Divide and Conquer

Contents

Introduction

Divide-and-conquer

Divide and conquer diagram

Problem-Solving Template

D&C problem-solving template

Divide and conquer template diagram

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

Recursion tree example

Method 3: Guess and test

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} \]
  1. $f(n)$ is polynomially smaller than $n^{\Delta}$ $\implies T(n) \in \Theta(n^{\Delta})$
  2. $f(n)$ is asymptotically close to $n^{\Delta}$ $\implies T(n) \in \Theta(f(n) \log n)$
  3. $f(n)$ is polynomially larger than $n^{\Delta}$ $\implies T(n) \in \Theta(f(n))$
Master theorem recursion tree

Problems

Solve $T(n) = T(n/2) + 1$ using the master theorem


Solve $T(n) = 2T(n/2) + 1$ using the master theorem


Solve $T(n) = 2T(n/2) + n$ using the master theorem


Solve $T(n) = 2T(n/2) + n^2$ using the master theorem


Solve the following recurrences using the master theorem

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

Array sum 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

Array sum recursion 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} \]

Merge Sort

Problem

Sort the elements of an array in nondecreasing order.

Step 1. Subproblem

\[ \begin{aligned} &\mathrm{Sort}(A[\ell \ldots h]) = \text{Sort all elements in subarray } A[\ell \ldots h]\\ &\text{Compute } \mathrm{Sort}(A[1 \ldots n]) \end{aligned} \]

Step 2. Recursive formulation

Merge sort recursive formulation

Step 3. Algorithm

\begin{algorithm}
\begin{algorithmic}

\FUNCTION{MergeSort}{$A[low \ldots high]$}
\IF{$low = high$}
    \RETURN $A[low \ldots high]$
\ENDIF
\IF{$low < high$}
    \STATE $mid \gets \lfloor (low+high)/2 \rfloor$
    \STATE $n \gets high-low+1$
    \STATE $B[1 \ldots \lceil n/2 \rceil] \gets$ \CALL{MergeSort}{$A[low \ldots mid]$}
    \STATE $C[1 \ldots \lfloor n/2 \rfloor] \gets$ \CALL{MergeSort}{$A[mid+1 \ldots high]$}
    \STATE \CALL{Merge}{$B[1 \ldots \lceil n/2 \rceil], C[1 \ldots \lfloor n/2 \rfloor], A[low \ldots high]$}
\ENDIF
\ENDFUNCTION

\end{algorithmic}
\end{algorithm}


\begin{algorithm}
\begin{algorithmic}

\FUNCTION{Merge}{$B[1 \ldots p], C[1 \ldots q], A[1 \ldots (p+q)]$}
\STATE $i \gets 1$; $j \gets 1$; $k \gets 1$
\WHILE{$i \leq p$ \AND $j \leq q$}
    \IF{$B[i] \leq C[j]$}
        \STATE $A[k] \gets B[i]$
        \STATE $i \gets i+1$
    \ELSE
        \STATE $A[k] \gets C[j]$
        \STATE $j \gets j+1$
    \ENDIF
    \STATE $k \gets k+1$
\ENDWHILE
\IF{$i = (p+1)$}
    \STATE $A[k \ldots (p+q)] \gets C[j \ldots q]$
\ELSE
    \STATE $A[k \ldots (p+q)] \gets B[i \ldots p]$
\ENDIF
\ENDFUNCTION

\end{algorithmic}
\end{algorithm}

Step 4. Example

Merge sort example


Merge sort example

Step 5. Complexity

\[ \begin{aligned} &\text{Time } T(n) = \left. \begin{cases} \Theta(1) & \text{if } n = 1,\\ 2T(n/2) + \Theta(n) & \text{if } n > 1. \end{cases} \right\} \in \Theta(n \log n) \\ &\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(n) \end{aligned} \]

Quicksort

Problem

Sort the elements of an array in nondecreasing order.

Step 1. Subproblem

\[\begin{array}{l}\mathrm{Sort}(A[\ell \ldots h]) = \text{Sort all elements in subarray } A[\ell \ldots h]\text{ in nondecreasing order.}\\\text{Compute } \mathrm{Sort}(A[1 \ldots n])\end{array}\]

Step 2. Recursive formulation

Quick sort recursive formulation

Step 3. Algorithm

\begin{algorithm}
\begin{algorithmic}

\FUNCTION{QuickSort}{$A[low \ldots high]$}
\IF{$low < high$}
    \STATE $s \gets$ \CALL{Partition}{$A[low \ldots high]$}
    \STATE \CALL{QuickSort}{$A[low \ldots s]$}
    \STATE \CALL{QuickSort}{$A[s+1 \ldots high]$}
\ENDIF
\ENDFUNCTION

\end{algorithmic}
\end{algorithm}


\begin{algorithm}
\begin{algorithmic}

\FUNCTION{Partition}{$A[low \ldots high]$}
\STATE $pivot \gets A[low]$
\STATE $i \gets low$; $j \gets high+1$
\WHILE{\TRUE}
    \STATE $i \gets i+1$
    \WHILE{$A[i] < pivot$}
        \IF{$i = high$}
            \STATE \textbf{break}
        \ENDIF
    \ENDWHILE
    \STATE $j \gets j-1$
    \WHILE{$pivot < A[j]$}
        \IF{$j = low$}
            \STATE \textbf{break}
        \ENDIF
    \ENDWHILE
    \IF{$i \geq j$}
        \STATE \textbf{break}
    \ENDIF
    \STATE \CALL{Swap}{$A[i], A[j]$}
\ENDWHILE
\STATE \CALL{Swap}{$A[low], A[j]$}
\RETURN $j$
\ENDFUNCTION

\end{algorithmic}
\end{algorithm}

Step 4. Example

Quick sort example


Randomized partition illustration.


Hoare partition

Step 5. Complexity

\[ \begin{aligned} &\text{Time } T(n) \le \left. \begin{cases} \Theta(1) & \text{if } n = 1,\\ T(n-1) + \Theta(n) & \text{if } n > 1. \end{cases} \right\} \in O(n^2) \\ &\text{Space } S(n) \le \left. \begin{cases} \Theta(1) & \text{if } n = 1,\\ S(n-1) + \Theta(1) & \text{if } n > 1. \end{cases} \right\} \in O(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] \]

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} \]
Integer multiplication recursive formulation

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)$

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

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} \]
Karatsuba recursive formulation

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}

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)\\ &= (11 \times 10)\cdot 2^4 + \left( \begin{array}{c} (11 + 00)\times(10 + 01)\\ - 11 \times 10 - 00 \times 01 \end{array} \right)\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,\\ 3T(n/2) + \Theta(n) & \text{if } n > 1. \end{cases} \right\} \in \Theta(n^{\log_2 3}) \\ &\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(n) \end{aligned} \]