Divide and Conquer

| Prerequisite Readings | Additional Readings | |—————|———-| | Recursions | CLRS (4.2)
Skiena (5)
Sedgewick (2.1, 2.2) |

🤓☝️ The GIST For some problem $\Pi$, split $\Pi$ into independent1 subproblems ($\pi_1, \pi_2, \dots, \pi_n$) until these subproblems are base cases. This is done recursively, which are trivial to solve2. The results of these are then combined to solve $\Pi$.

To easily understand Divide and Conquer, we won’t concretely define it, but we will look at how this paradigm is used instead.

Binary Search is one of the simplest algorithms you should know. Binary search takes in a sorted sequence or set $A$ and a key $k$, and it ensures to return the index $i$ if $S[i] = k$ or $\texttt{NIL}$ if for every $i\in A, S[i] \ne k$. It does this by getting the middle index $m$, the leftmost index $l$, and the rightmost index $r$ and checks if $A[m] = k$. If this equality is true, then it has found the answer and terminates. Otherwise, check $A[m]>k$, if this is true check recursively call the algorithm on $A[l, m-1]$. And when, $A[m]<k$ call instead on $A[m+1, h]$.

Algorithm: $\textbf{Recursive-Binary-Search}$ Requires: A sorted sequence or set $A$ and a key $k$. Ensures: Index $i$ s.t. $A[i] = k$ or $\texttt{NIL}$ if $\forall i, A[i] \ne k$.

  1. $\textbf{if } l > h \textbf{ then}$
    1. $\textbf{return } \texttt{NIL}$
  2. $m \gets l + \lfloor \frac{h-l}{2}\rfloor$
  3. $\textbf{if } A[m] = k \textbf{ then}$
    1. $\textbf{return } m$
  4. $\textbf{else if } A[m] < k \textbf{ then}$
    1. $\textbf{return } \text{Recursive-Binary-Search}(A,k,m+1,h)$
  5. $\textbf{else}$
    1. $\textbf{return } \text{Recursive-Binary-Search}(A,k,l,m-1)$

The idea here is that our search space (the size of $A$) decreases by half every recursive call. That is, as the recursive algorithm goes on, the search space (initially $A\texttt{.len}$) is reduces by $\frac{1}{2^n}$ where $n$ is the number of recursive calls. Hence, for the fourth recursive call we will have reduced the search space to $A\texttt{.len}\frac{1}{16}$.

Solving for the time complexity of $\text{Recursive-Binary-Search}$ we get $\mathcal{O}(\lg n)$.

Let’s think of sorting, a “base case” for all sorting algorithms is the element containing one or zero elements. This is “trivial to solve” since the answer takes $\mathcal O(1)$ to solve (it’s the array itself)!

AI Use Declaration. See AI Use Declaration

  1. This will not make sense for now, but after reading up on Dynamic Programming go back here to think about why I emphasize the word “independent”. ↩

  2. “Trivial to solve” essentially means that the problems are so small that it does not take make “brain power” or computation to figure out how to solve it. ↩