summaryrefslogtreecommitdiff
path: root/info/mathtrip/src/recur1.tex
blob: 6cafb0e27a119eef8391d302c25c4089ef0d5067 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
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}
   }%
}