MIT 6.046 - Design and Analysis of Algorithms

A recurrence relation is an equation or inequality that describes a function in terms of its value on smaller inputs. It's commonly used to analyze the running time of recursive algorithms. For example, the running time of Merge Sort can be described by $T(n)=2T(n/2)+O(n)$.

The Substitution Method involves guessing a solution (e.g., $T(n)=O(n\log n)$) and then using mathematical induction to prove that the guess is correct. It requires good intuition for making the initial guess and verifying it with base cases and inductive steps.

The Recursion Tree Method visualizes the recursive calls as a tree, where each node represents the cost of a subproblem. Summing the costs at each level of the tree and then summing the costs of all levels gives the total running time. It's useful for generating good guesses for the Substitution Method.

For recurrences $T(n)=aT(n/b)+f(n)$ where $a\ge 1$, $b>1$, and $f(n)$ is asymptotically positive:
1. If $f(n)=O(n^{{\log }_{b}a-ϵ})$ for some constant $ϵ>0$, then $T(n)=\Theta (n^{{\log }_{b}a})$.
2. If $f(n)=\Theta (n^{{\log }_{b}a}{\log }^{k}n)$ for some constant $k\ge 0$, then $T(n)=\Theta (n^{{\log }_{b}a}{\log }^{k+1}n)$.
3. If $f(n)=\Omega (n^{{\log }_{b}a+ϵ})$ for some constant $ϵ>0$, AND $af(n/b)\le cf(n)$ for some constant $c<1$ and sufficiently large $n$ (regularity condition), then $T(n)=\Theta (f(n))$.

Here $a=4$, $b=2$, $f(n)=O(n)$.
Compare $f(n)$ with $n^{{\log }_{b}a}=n^{{\log }_{2}4}=n^2$.
Since $f(n)=O(n)=O(n^{2-ϵ})$ for $ϵ=1$, this falls under Case 1.
Thus, $T(n)=\Theta (n^{{\log }_{b}a})=\Theta (n^2)$.

Here $a=2$, $b=2$, $f(n)=O(n)$.
Compare $f(n)$ with $n^{{\log }_{b}a}=n^{{\log }_{2}2}=n^1=n$.
Since $f(n)=O(n)=\Theta (n^{{\log }_{b}a}{\log }^{0}n)$, this falls under Case 2 with $k=0$.
Thus, $T(n)=\Theta (n^{{\log }_{b}a}{\log }^{0+1}n)=\Theta (n\log n)$.

Here $a=1$, $b=2$, $f(n)=O(n)$.
Compare $f(n)$ with $n^{{\log }_{b}a}=n^{{\log }_{2}1}=n^0=1$.
Since $f(n)=O(n)=\Omega (n^{0+ϵ})$ for $ϵ=1$, this falls under Case 3.
Check regularity condition: $af(n/b)\le cf(n)⟹1\cdot O(n/2)\le c\cdot O(n)$. This holds for $c=1/2<1$.
Thus, $T(n)=\Theta (f(n))=\Theta (n)$.

Dynamic Programming applies to problems exhibiting:
1. Optimal Substructure: An optimal solution to the problem contains optimal solutions to subproblems.
2. Overlapping Subproblems: The recursive algorithm revisits the same subproblems repeatedly. DP solves each subproblem only once and stores its solution.