%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}
  }%
}

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.