diff options
Diffstat (limited to 'info/mathtrip/src/recur1.tex')
-rw-r--r-- | info/mathtrip/src/recur1.tex | 177 |
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} + }% +} |