summaryrefslogtreecommitdiff
path: root/info/mathtrip/src/recur1.tex
diff options
context:
space:
mode:
Diffstat (limited to 'info/mathtrip/src/recur1.tex')
-rw-r--r--info/mathtrip/src/recur1.tex177
1 files changed, 177 insertions, 0 deletions
diff --git a/info/mathtrip/src/recur1.tex b/info/mathtrip/src/recur1.tex
new file mode 100644
index 0000000000..6cafb0e27a
--- /dev/null
+++ b/info/mathtrip/src/recur1.tex
@@ -0,0 +1,177 @@
+%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}
+ }%
+}