> [!NOTE] Definition > An divide & conquer [[Algorithm for Computational Problem|algorithm]] of the form: ```pseudo \begin{algorithm} \begin{algorithmic} \Procedure{p}{input $x$ of size $n$} \If{$n$ < some constant $k$} \State Solve $x$ directly without recusrion \Else \State Create $a$ subproblems of $x$, each having size $n/b$ \\ Call procedure $p$ recursively on each subproblem\\ Combine the results from the subproblems \EndIf \EndProcedure \end{algorithmic} \end{algorithm} ``` # Properties For runtime analysis, see [[Master Theorem for Polynomial Work]]. # Examples - [[Merge Sort]]; - [[Binary Search]]; - [[Randomized Quicksort]]; - [[Maximum Subarray Sum & Kadane's Algorithm]]. - [[Strassen Algorithm]].