„Algoritmuselmélet - Vizsga, 2013.05.30.” változatai közötti eltérés
| 69. sor: | 69. sor: | ||
<math>\sum_{i=0}^{k} r^i = \frac{1-r^{k+1}} {1-r} </math>, ahol <math> k = \left \lfloor log_4n \right \rfloor, r = \frac{1}{16}</math>, vagyis <math>\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}}</math><br> | <math>\sum_{i=0}^{k} r^i = \frac{1-r^{k+1}} {1-r} </math>, ahol <math> k = \left \lfloor log_4n \right \rfloor, r = \frac{1}{16}</math>, vagyis <math>\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}}</math><br> | ||
<math>\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}} | <math>\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}} < 2 ,</math><big>ha</big> <math> n \geq 1</math> | ||
Tehát <math> T(n)=...=1+2 \cdot O(n^2)=O(n^2)</math> | Tehát <math> T(n)=...=1+2 \cdot O(n^2)=O(n^2)</math> | ||