%This commad provides the text in the first column of the recurences
%
%This command has one parameter:
% 1) The width of the text
\newcommand\TTwoRecurOne[1]{%
\parbox[t]{#1}{%
\TTwoRecurenceFontSize
%This command add a small line between 2 paragraphs to
%better separate different elements.
\def\Filet{\par\centerline{\rule{5em}{.5pt}}\par}
\deflength{\parskip}{\TTwoRecurParSkip}
%We accept a unbalanced last column
%\defcounter{unbalance}{2}
%Width of the vertical rule to separate columns.
\deflength{\columnseprule}{.4pt}
\DisplaySpace{\TTwoDisplaySpace}{\TTwoDisplayShortSpace}
\begin{multicols}{3}
\TTwoTitle{Master method:}
\AdjustSpace{-.75ex plus .25 ex minus .5ex}
\begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\SmallChar}{\StyleWithoutNumber}
\Fm{T(n) = aT(n/b) + f(n)}
\Fm{\MathRemark[\relax]{a\geq 1, b > 1}}
\end{DisplayFormulae}
\Filet
\begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\SmallChar}{\StyleWithoutNumber}
\unskip If \Fm[true]{\exists\, \epsilon > 0} such that \Fm[true]{f(n) = O(n^{\log_b a - \epsilon})}
then: \Fm[true]{T(n) = \Theta(n^{\log_b a})}
\end{DisplayFormulae}
\Filet
\begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\SmallChar}{\StyleWithoutNumber}
\unskip If \Fm[true]{f(n) = \Theta(n^{\log_b a})} then
\Fm[true]{T(n) = \Theta(n^{\log_b a} \log_2 n)}
\end{DisplayFormulae}
\Filet
\begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\SmallChar}{\StyleWithoutNumber}
\unskip If \Fm[true]{\exists\, \epsilon > 0} such that
\Fm[true]{f(n) = \Omega(n^{\log_b a + \epsilon})},
and \Fm[true]{\exists\, c < 1} such that \Fm[true]{a f(n/b) \leq cf(n)} for large $n$,
then:
\Fm[true]{T(n) = \Theta(f(n))}
\end{DisplayFormulae}
\TTwoTitle{Substitution \textup{(}example\textup{)}:}
\begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\SmallChar}{\StyleWithoutNumber}
\unskip Consider the following recurrence:\\
\Fm[true]{T_{i+1} = 2^{2^i} \cdot T_i^2\MathRemark{T_1 = 2}}.
Note that $T_i$ is always a power of two.
\end{DisplayFormulae}
\begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\SmallChar}{\StyleWithoutNumber}
\unskip Let \Fm[true]{t_i = \log_2 T_i}.
Then we have:
\Fm[true]{t_{i+1} = 2^i + 2 t_i\MathRemark{t_1 = 1}}
\end{DisplayFormulae}
\begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\SmallChar}{\StyleWithoutNumber}
\unskip Let \Fm[true]{u_i = t_i/2^i}.
Dividing both sides of the previous equation by \Fm[true]{2^{i+1}} we get:
\Fm[true]{\frac{t_{i+1}}{2^{i+1}} = \frac{2^i}{2^{i+1}} + \frac{t_i}{2^i}}
\end{DisplayFormulae}
\begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\SmallChar}{\StyleWithoutNumber}
\unskip Substituting we find:\\%[-1ex plus .5ex minus .5ex]
\Fm[true]{u_{i+1} = 2^{-1} + u_i\MathRemark{u_1 = 2^{-1}}},
which is simply \Fm[true]{u_i = i/2}.
So we find that \Fm[true]{T_i} has the closed form \Fm[true]{T_i = 2^{i2^{i-1}}}.
\end{DisplayFormulae}
\TTwoTitle{Summing factors \textup{(}example\textup{)}:}
\begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\BigChar}{\StyleWithoutNumber}
\unskip Consider the following recurrence:\\
\Fm[true]{T(n) = 3T(n/2) + n\MathRemark{T(1) = 1}}
\end{DisplayFormulae}
\begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\BigChar}{\StyleWithoutNumber}
\unskip Rewrite so that all terms involving $T$ are on the
left side:\\
\Fm[true]{T(n) - 3T(n/2) = n}
Now expand the recurrence,
and choose a factor which makes the left side ``telescope''.
\end{DisplayFormulae}
\begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\BigChar}{\StyleWithoutNumber}
\Fm{\left(T(n) - 3T(n/2) = n\right)}
\def\FormulaRecur{\left(T(n/2) - 3T(n/4) = n/2\right)}
\Fm{\FormulaRecur}
%To get the size of the preceding formula
\WriteFormula{0pt}{\TmpLengthA}{\FormulaRecur}{false}
\Fm{\makebox[\TmpLengthA][c]{$\vdots$}}
\Fm{3^{\log_2 n - 1}\left(T(2) - 3T(1) = 2\right)}
\end{DisplayFormulae}
\begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\SmallChar}{\StyleWithoutNumber}
\unskip Let \Fm[true]{m = \log_2 n}.
Summing the left side we get:
\def\FirstPart{T(n) - 3^mT(1)}
\FmPartA{\FirstPart= T(n) - 3^m}
\FmPartB{\FirstPart}{= T(n) - n^k}\\
\MathRemark[\relax]{\text{where } k = \log_2 3 \approx 1\SepDecimal 58496}.
\end{DisplayFormulae}
Summing the right side we get:\\
\begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\BigChar}{\StyleWithoutNumber}
\Fm{\sum_{i=0}^{m-1} \frac{n}{2^i} 3^i = n \sum_{i=0}^{m-1} \left(\frac{3}{2} \right)^i}
\end{DisplayFormulae}
\begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\BigChar}{\StyleWithoutNumber}
\unskip Let \Fm[true]{c = \frac{3}{2}}.
Then we have:
\def\FirstPart{n \sum_{i=0}^{m-1} c^i}
\FmPartA{\FirstPart = n \left( \frac{c^m-1}{c-1} \right)}
\FmPartB{\FirstPart}{= 2 n \left( c^{\log_2 n } - 1 \right)}
\FmPartB{\FirstPart}{= 2 n \left( c^{(k-1) \log_c n } - 1 \right)}
\FmPartB{\FirstPart}{= 2 n^k - 2n}
and so \Fm[true]{T(n) = 3 n^k - 2n}.
\end{DisplayFormulae}
Full history recurrences can often be changed to limited history ones.
\TTwoTitle{Example:}
\AdjustSpace{-1.5ex plus .5ex minus .5ex}
\begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\BigChar}{\StyleWithoutNumber}
\unskip Consider:
\Fm{T_i = 1 + \sum^{i-1}_{j=0} T_j\MathRemark{T_0 = 1}}\\
Note that:
\Fm{T_{i+1} = 1 + \sum^i_{j=0} T_j}\\
By subtracting we find:
\def\FirstPart{T_{i+1} - T_i}
\FmPartA{\FirstPart = 1 + \sum^i_{j=0} T_j - 1 - \sum^{i-1}_{j=0} T_j}
\FmPartB{\FirstPart}{= T_i}\\
And so \Fm[true]{T_{i+1} = 2T_i = 2^{i+1}}.
\end{DisplayFormulae}
\TTwoTitle{Generating functions:}
\begin{enumerate}[noitemsep,nolistsep]
\item Multiply both sides of the equation by $x^i$.
\item Sum both sides over all $i$ for which the equation is valid.
\item Choose a generating function $G(x)$.
Usually $G(x) = \sum_{i=0}^\infty x^i g_i$.
\item Rewrite the equation in terms of the generating function $G(x)$.
\item Solve for $G(x)$.
\item The coefficient of $x^i$ in $G(x)$ is $g_i$.
\end{enumerate}
\TTwoTitle{Example:}
\begin{DisplayFormulae}{1}{0pt}{2ex plus 1ex minus 1ex}{\BigChar}{\StyleWithoutNumber}
\unskip
Let the equation: \\
\Fm{g_{i+1} = 2 g_i + 1\MathRemark{g_0 = 0}}.\\[.6ex plus .2ex minus .1ex]
Multiply and sum:
\Fm{\sum_{i\geq 0} g_{i+1} x^i = \sum_{i\geq 0} 2 g_i x^i + \sum_{i\geq 0} x^i}
We choose: \Fm[true]{G(x) = \sum_{i\geq 0} x^i g_i}.\\
Rewrite in terms of \Fm[true]{G(x)}:
\Fm{\frac{G(x)-g_0}{x} = 2 G(x) + \sum_{i\geq 0} x^i}\\
Simplify:
\Fm{\frac{G(x)}{x} = 2 G(x) + \frac{1}{1-x}}\\
Solve for \Fm[true]{G(x)}:
\Fm{G(x) = \frac{x}{(1-x)(1-2x)}}.\\
Expand this using partial fractions:
\def\FirstPart{G(x)}
\FmPartA{\FirstPart = x \left(\frac{2}{1-2x} - \frac{1}{1-x}\right)}
\FmPartB{\FirstPart}{= x \left(2 \sum_{i\geq 0} 2^i x^i - \sum_{i\geq 0} x^i\right)}
\FmPartB{\FirstPart}{= \sum_{i\geq 0} (2^{i+1} - 1) x^{i+1}}\\
So \Fm[true]{g_i = 2^i - 1}.
\end{DisplayFormulae}
\end{multicols}
}%
}