Určovanie počtu operácií v rekurzívnych volaniach

Vyjadrenie funkcie $T(n)$ analyticky (nerekurzívne), geometrická postupnosť, určovanie výpočtovej zložitosti v rekurzívnych funkciách.

Určenie konkrétnej hodnoty rekurzívnej funkcie výpočtovej zložitosti

Už vieme určovať výpočtovú zložitosť v metódach, ktoré nie sú rekurzívne. Ale čo ak funkcia volá samú seba? Majme napríklad funkciu $T(n)$ definovanú takto:

$\begin{array}{rl}T(n)& =T(n-1)+5\\ T(1)& =3\\ \end{array}$

Funkcia $T(n)$ odkazuje na samú seba, pričom vieme že pre $n=1$ je hodnota číslo 3. Toto sa nazýva triviálny prípad – je to bod, v ktorom sa rekurzívne volanie zastaví. Toto bude veľmi dôležité, pretože rekurzívne funkcie sa musia skôr či neskôr zastaviť (nemôžeme ich volať donekonečna).

Aby sme si vedeli lepšie predstaviť ako rekurzívne funkcie fungujú, poďme vypočítať, akú hodnotu bude mať $T(5)$:

$\begin{array}{rl}T(n)& =T(n-1)+5\\ T(1)& =3\\ T(2)& =T(2-1)+5=T(1)+5=3+5=8\\ T(3)& =T(3-1)+5=T(2)+5=8+5=13\\ T(4)& =T(4-1)+5=T(3)+5=13+5=18\\ T(5)& =T(5-1)+5=T(4)+5=18+5=23\\ \end{array}$

Ako vidíme, $T(5)=23$. Ide iba o postupné nahrádzanie premennej $n$, pričom ak chceme vypočítať určitú hodnotu, musíme v tomto prípade poznať aj všetky predošlé hodnoty. Avšak, čo by sa stalo ak by sme chceli vypočítať $T(1000)$? Ak by sme to počítali manuálne, trvalo by to strašne dlho. Veľmi veľké hodnoty by robili problém aj najrýchlejším počítačom, obzvlášť ak by rekurzívne volania boli komplikovanejšie.

Našťastie, pre tento prípad vieme rekurzívne funkcie vyjadriť analyticky (teda, nerekurzívne) – to znamená že pre dané $n$ vieme vypočítať konkrétnu hodnotu bez toho, aby sme volali funkciu rekurzívne.

Pri analýze funkcie musíme postupovať od čísla $n$ a postupne sa vnárať hlbšie a hlbšie do rekurzie. Pre príklad vyššie by sme postupovali takto:

$$\begin{array}{rl}T(n)& =T(n-1)+5\\ T(n-1)& =?\\ \end{array}$$

Ako všeobecne vyjadríme $T(n-1)$? Tak, že zoberieme všeobecnú definíciu funkcie $T(n)$ a namiesto $n$ dosadíme $n-1$:

$$\begin{array}{rl}T(n)& =T(n-1)+5\\ T(n-1)& =T(\underset{n}{\underbrace{n-1}}-1)+5\\ T(n-1)& =T(n-2)+5\\ \end{array}$$

To dáva zmysel – ak chceme vyjadriť $T(n-1)$, musíme k hodnote predtým ($T(n-2)$) pripočítať 5. Inými slovami, vždy sa hodnota pre nejaké $n$ vyjadrí tak, že sa k hodnote predtým ($n-1$) pripočíta 5. Ale nesmieme zabudnúť, že $T(1)=3$.

Ak by sme pokračovali vo vyjadrovaní menších a menších $n$, vyzeralo by to nejako takto. $n$ znižujeme preto, lebo sa chceme priblížiť ku triviálnemu prípadu: číslu 3 (predpokladá sa, že $3<n$):

$\begin{array}{rl}T(n-1)& =T(n-2)+5\\ T(n-2)& =T(n-3)+5\\ T(n-3)& =T(n-4)+5\\ \end{array}$

Teraz sme si vyjadrili pomocné funkcie a vnorili sa hlbšie do rekurzie. Tieto funkcie musíme dosadiť späť do pôvodného $T(n)$, teda:

$$\begin{array}{rl}T(n)& =T(n-1)+5\\ & =T(n-2)+5+5\\ & =T(n-3)+5+5\\ & =T(n-4)+5+5+5\\ \cdots \\ \end{array}$$

A takto to bude pokračovať donekonečna... Ale nie? Kedy sa rekurzia skončí? Skončí sa vtedy, keď nastane triviálny prípad. Triviálny prípad je v tomto prípade $T(1)=3$. To znamená, že funkcia nebude volať samú seba, ak $n=1$ (pretože vráti iba číslo 3).

To znamená, že do nášho rozpisu musíme namiesto posledného rekurzívneho volania dať triviálny prípad:

$$T(n)=\stackrel{\text{sem}}{\overbrace{T(n-4)}}+5+5+5$$

Vsunieme tam $T(1)$ (čo je vlastne číslo 3) pretože to je jediný prípad ktorý neobsahuje rekurziu. Vďaka tomu bude funkcia vyjadrená nerekurzívne (analyticky):

$$T(n)=\stackrel{3}{\overbrace{T(1)}}+5+5+5+\cdots$$

Posledná otázka je, že koľkokrát sa tam bude nachádzať sčítanie čísla 5. Ak sa pozrieme na pôvodné výpočty vyššie, vidíme že čísiel 5 je tam vždy o 1 menej ako $n$:

$$\begin{array}{rl}T\stackrel{n=1}{\overbrace{(1)}}& =3\\ T(2)& =T(\stackrel{n=2}{\overbrace{n-1}})+\stackrel{n-1}{\overbrace{5}}\\ T(3)& =T(\stackrel{n=3}{\overbrace{n-2}})+\stackrel{n-1}{\overbrace{5+5}}\\ T(4)& =T(\stackrel{n=4}{\overbrace{n-3}})+\stackrel{n-1}{\overbrace{5+5+5}}\\ T(5)& =T(\stackrel{n=5}{\overbrace{n-4}})+\stackrel{n-1}{\overbrace{5+5+5+5}}\\ \cdots \\ \end{array}$$

Funkciu $T(n)$ môžeme teda zapísať ako:

$$\begin{array}{rl}T(n)& =T(1)+5\times (n-1)\\ & =3+5\times (n-1)\\ & =3+5n-5\\ T(n)& =5n-2\\ \end{array}$$

Bohužiaľ, nepomôže nič iné ako iba pozrieť sa na funkciu a všimnúť si vzťah medzi $n$ a postupnosťou čísiel. Odporúčam pre rekurziu vypočítať viacero príkladov, keďže sú to veci nad ktorými sa treba zamyslieť logicky a pre netrénované oko to môže byť náročnejšie.

Posledný krok kde sme určili že tam bude $5\times (n-1)$ môže byť zatiaľ dosť ťažké na pochopenie. Poďme preto na ďalší príklad, kde si ukážeme ako sa nad tým dá uvažovať trochu inak:

$$\begin{array}{rl}T(1)& =0\\ T(n)& =T(n-1)+n-1\\ \end{array}$$

Vidíme, že triviálny prípad je $T(1)=0$. Poďme teda postupne vyjadrovať $T(n-1)$, $T(n-2)$, $T(n-3)$... Vždy za $n$ v pôvodnom vzorci dosadíme aktuálny argument vo funkcii ktorú vyjadrujeme:

$$\begin{array}{rl}T(n)& =T(n-1)+n-1\\ T(n-1)& =T((n-1)-1)+(n-1)-1\\ & =T(n-2)+n-2\\ T(n-2)& =T((n-2)-1)+(n-2)-1\\ & =T(n-3)+n-3\\ \\ \\ \\ T(n-3)& =T(n-4)+n-4\\ T(n-4)& =T(n-5)+n-5\\ & \cdots \end{array}$$

Funkcie hore teraz dosádzame na miesto rekurzívnych funkcií v pôvodnom výraze $T(n)$. Inými slovami, teraz nebudeme nahrádzať jednotlivé $n$, ale rovno celé $T(...)$ funkcie namiesto ekvivalentov vyššie:

$$\begin{array}{rl}T(n)& =T(n-1)+n-1\\ & =\stackrel{T(n-1)}{\overbrace{T(n-2)+n-2}}+n-1\\ & =\stackrel{T(n-2)}{\overbrace{T(n-3)+n-3}}+n-2+n-1\\ & =\stackrel{T(n-3)}{\overbrace{T(n-4)+n-4}}+n-3+n-2+n-1\\ & \cdots \\ \end{array}$$

...a takto budeme pokračovať až po triviálny prípad – $T(1)=0$. Ale poďme skúsiť niečo iné, namiesto obyčajného nahradenia $T(n-4)$ za $T(1)$.

Majme posledný riadok v našom výpočte vyššie:

$$T(n)=T(n-4)+n-4+n-3+n-2+n-1$$

Je to skoro akoby sa nám tam rysovala naša známa aritmetická postupnosť. Posledný prvok bude určite $n-1$, tak to je aj v pôvodnej funkcii $T(n)=T(n-1)+n-1$, za týmto už nič nie je takže $n-1$ musí byť posledný prvok. Ale ktorý prvok bude prvý? Teoreticky to je $T(n-4)$, ale tu je problém – je to funkcia, nie konkrétny prvok! Ako sa bude táto funkcia rozbaľovať, tak v sebe môže mať ešte veľmi dlhú postupnosť, napríklad niečo takéto:

$$T(n)=\cdots +n-7+n-6+n-5+n-4+n-3+n-2+n-1$$

Táto postupnosť musí skončiť pri $T(1)=0$. Takže, vyzerá nejako takto:

$$T(n)=0+\cdots +n-2+n-1$$

Hmm, to vyzerá jednoduchšie, ale ešte stále nemáme možnosť, ako môžeme nerekurzívne vyjadriť aká bude dlhá postupnosť. Vráťme sa teda o krok späť, kde sme ešte mali rekurzívne volanie:

$$T(n)=T(n-4)+n-4+n-3+n-2+n-1$$

Otázka je: existuje možnosť ako dosadiť do $n-4$ aby výsledok tohto výrazu bol 1 (triviálny prípad)? Ak v matematike odčítame dve rovnaké čísla, výsledok bude 0 ($1-1=0$, $123-123=0$, $\pi -\pi =0$...). Takže, toto musí platiť aj pre $n-n=0$. Ako z nuly spravíme jednotku? No, tak že ju k nej pripočítame: $n-n+1=1$. A jednotka je náš triviálny prípad! Ideme to dosadiť, aby bolo jasné čo si pod tým predstavujeme:

$$T(n)=\stackrel{T(1)=0}{\overbrace{T(n-n+1)}}+\cdots +n-4+n-3+n-2+n-1$$

Ach, zasa tie tri bodky! Ak by tam neboli, tak by sme predsa nevedeli že aká veľká postupnosť je za triviálnym prípadom. Pretože momentálne sme povedali iba to, čo už vieme – je nejaká nula a za ňou ide postupnosť $n$ ktoré sa zakaždým znižujú menej a menej, až po $n-1$. Počkať, ale veď v pôvodnom zápise sme $n-4$ nahradili $n-n+1$ aby sme dostali triviálny prípad. Mohli by sme to spraviť aj pre tú ďalšiu $n-4$? Áno, v podstate sa jedná o dva rovnaké zápisy, takže aj výsledok musí byť v tomto prípade rovnaký. Čiže:

$$T(n)=\stackrel{T(1)}{\overbrace{T(n-n+1)}}+\stackrel{\text{predtým:}n-4}{\overbrace{n-n+1}}+\cdots +n-3+n-2+n-1$$

Aha, takže teraz v podstate dopĺňame tú postupnosť z opačného konca! Takže by to pokračovalo nejako takto:

$$T(n)=\stackrel{T(1)}{\overbrace{T(n-n+1)}}+\stackrel{1}{\overbrace{n-n+1}}+\stackrel{2}{\overbrace{n-n+2}}+\stackrel{3}{\overbrace{n-n+3}}+\cdots +n-2+n-1$$

Poďme vyjadriť to čo vieme vyjadriť a dosadiť čo môžeme dosadiť, aby sme si to opäť zjednodušili:

$$T(n)=\stackrel{T(1)}{\overbrace{0}}+\stackrel{\text{aritmetická postupnosť}}{\overbrace{1+2+3+\cdots +n-2+n-1}}$$

Ha! Je to postupnosť čísiel! Vidíme dokonca medzeru medzi nulou a jednotkou. To znamená, že aritmetická postupnosť je iba vyznačená časť a iba na tú môžeme aplikovať vzorec. Prvý prvok je $1$, posledný $n-1$. To znamená, že výsledná nerekurzívna funkcia bude:

$$T(n)=0+\frac{(1+(n-1))\times n)}{2}$$

Hups, čo bude v tejto postupnosti počet prvkov ($n$)? Nemôže to byť rovnaké $n$ ako z $T(n)$, pretože to nevyjadruje počet prvkov našej aritmetickej postupnosti – tá postupnosť je iba pod-súčasťou celej funkcie. Teda naozajstná otázka je: koľko je čísiel od $1$ po $n-1$? Odpoveď: $\text{horná hranica}-\text{dolná}+1$. Takže: $n-1-1+1=n-1$. Pokračujeme:

$$\begin{array}{rl}T(n)& =\cancel{0+}\frac{(1+(n-1))\times (n-1))}{2}\\ & =\frac{n\times (n-1)}{2}\\ T(n)& =\frac{n^2-n}{2}\\ \end{array}$$

A to je aj naša odpoveď – tento vzorec môžeme teda použiť pre výpočet súčtu prvých $n$ prvkov, nerekurzívne (kde prvým prvkom je nula, takže $0+1+2+3+4+\cdots$). Toto riešenie je trochu zdĺhavejšie, ale zato veľmi detailné. Dokonca sme dokázali krok po kroku ako to celé funguje bez toho aby sme museli rátať prvých $n$ konkrétnych hodnôt.

Pre overenie či je naše riešenie naozaj správne, skúsme vypočítať nejakú hodnotu. Najskôr to vypočítame pomocou pôvodného rekurzívneho vzťahu a potom ich porovnáme – ak sa výsledky budú rovnať, naše riešenie je správne. Teda, povedzme že chceme vedieť hodnotu $T(5)$ (teda, $n=5$):

$$\begin{array}{rl}T(1)& =0\\ T(n)& =T(n-1)+n-1\\ T(2)& =T(2-1)+2-1=0+1=1\\ T(3)& =T(3-1)+3-1=1+2=3\\ T(4)& =T(4-1)+4-1=3+3=6\\ T(5)& =T(5-1)+5-1=6+4=10\\ \end{array}$$

Súčet prvých 5 prvkov je teda 10 ($0+1+2+3+4=10$, takže je to v poriadku). Teraz to vypočítajme pomocou našej funkcie:

$$\begin{array}{rl}T(n)& =\frac{n^2-n}{2}\\ T(5)& =\frac{5^2-5}{2}\\ & =\frac{25-5}{2}\\ & =\frac{20}{2}\\ & =10\end{array}$$

Výsledky sa zhodujú, takže to funguje a je to v poriadku. A určite je táto funkcia omnoho rýchlejšia ako jej pôvodná rekurzívna verzia.

Postup vyššie môže niekomu pomôcť, ale druhému zasa veci zkomplikovať. Spôsobov riešenia je viacero a na konci dňa záleží iba na výsledku – treba si vybrať ten, ktorý je pre danú situáciu najvhodnejší.

Poďme ďalej, späť na niečo menej zložité. Cieľom je opäť vyjadriť funkciu $T(n)$ analyticky (inými slovami: nerekurzívne):

$$\begin{array}{rl}T(1)& =5\\ T(n)& =T(n-1)+2\\ \end{array}$$

Keď sa na to pozrieme logicky, v podstate je to funkcia ktorá začína od čísla 5, pričom k predošlému výsledku vždy pripočíta číslo 2. Postupnosť hodnôt teda vyzerá nasledovne: $5,7,9,11,13,15,17,\cdots$. Poďme sa ale postupne vnárať do rekurzie – pre stručnosť už nebudem uvádzať výpočet "krok za krokom", ale princíp zostáva rovnaký ako v predošlých príkladoch; výsledkom by malo byť:

$$\begin{array}{rl}T(1)& =5\\ T(n)& =T(n-1)+2\\ & =T(n-2)+2+2\\ & =T(n-3)+2+2+2\\ & =T(n-4)+2+2+2+2\\ & \cdots \\ \end{array}$$

Už sa začína rysovať istá postupnosť čísiel, ktorá avšak nie je aritmetická – k číslu ktoré odčíta $n$ v rekurzívnej funkcii naľavo sa vždy pripočíta rovnaký počet dvojok. Kedy sa to zastaví? Vždy, keď nastane triviálny prípad $T(1)=5$. Otázka je jednoducho koľkokrát máme tie dvojky vynásobiť a na začiatku alebo konci k tomu pripočítame iba 5 a dostaneme našu funkciu. Ak na to ale máme ísť analyticky:

$$\begin{array}{rl}T(1)& =5\\ T(n)& =T(n-4)+2+2+2+2\\ & =T(n-4)+4\times 2\\ & =\stackrel{T(1)}{\overbrace{T(n-n+1)}}+?\times 2\end{array}$$

Nastal ale problém – chceme 4 nahradiť $n+1$, lenže nemôžme pretože sa to nespráva ako jeden prvok. Musíme okolo pridať zátvorky tak, aby výsledok zostal rovnaký a aby sa $n+1$ správalo ako jeden prvok:

$$T(n)=\stackrel{T(1)}{\overbrace{T(n-(n-1))}}+(n-1)\times 2$$

Teraz je to už v poriadku. Pretože pred zátvorkou je mínus, výsledok bude rovnaký ako v predošlej verzii – toto sme preniesli aj na miesto druhej 4 ako jeden prvok. Ak by sme to preniesli ako $(n+1)\times 2$, tak by to nevychádzalo – ak to nie je jasné, bohužiaľ pomôže opäť iba logické myslenie. Ale ako radu odporúčam pri "umelej tvorbe čísla 1" vždy používať $n-(n-1)$ namiesto $n-n+1$, aby sme sa vyhli zbytočným problémom akým bol napríklad aj tento.

Ale teraz už pokračujme:

$$\begin{array}{rl}T(n)& =5+(n-1)\times 2\\ T(n)& =5+2n-2\\ T(n)& =2n+3\\ \end{array}$$

Výsledok je teda $T(n)=2n+3$. Skúsme to porovnať s našou očakávanou postupnosťou čísel, ktorú sme odhadli úplne na začiatku. $5,7,9,11,13,15,17,\cdots$:

$$\begin{array}{rl}T(n)& =2n+3\\ T(1)& =2\times 1+3=5\\ T(2)& =2\times 2+3=7\\ T(3)& =2\times 3+3=9\\ T(4)& =2\times 4+3=11\\ T(5)& =2\times 5+3=13\\ \end{array}$$

Výsledky sa zhodujú, takže to asi bude platiť aj pre všetky ostatné $n$.

Geometrická postupnosť

V tomto bode sa stretávame s geometrickou postupnosťou. Je to postupnosť, kde sa namiesto základu mení exponent, respektíve prvky sa nemenia o nejaké číslo, ale menia sa o niekoľko krát.

Príkladom geometrickej postupnosti môže byť takto definovaná rekurzívna funkcia:

$$\begin{array}{rl}T(0)& =0\\ T(n)& =2\times T(n-1)+2\\ \end{array}$$

Triviálny prípad je $T(0)=0$, pričom vždy násobíme predošlý výsledok 2-krát a pripočítame k tomu dvojku. Ak rekurziu rozbalíme, bude vyzerať nejako takto:

$$\begin{array}{rl}T(n)& =2\times T(n-1)+2\\ & =2\times (\stackrel{T(n-1)}{\overbrace{2\times T(n-2)+2}})+2\\ & =2\times (\underset{T(n-1)}{\underbrace{2\times \stackrel{T(n-2)}{\overbrace{(2\times T(n-3)+2)}}+2}})+2\\ & \cdots \\ \end{array}$$

Pozor – keď násobíme dvojkou, násobíme celý predošlý výsledok! Takže nesmieme zabudnúť výrazy osádzať zátvorkami!

Ak by sme pokračovali, vyzeralo by to nejako takto:

$$\begin{array}{rl}& =2\times (2\times (2\times (2\times T(n-4)+2)+2)+2)+2\\ & =2\times (2\times (2\times (2\times (2\times T(n-5)+2)+2)+2)+2)+2\\ & \cdots \\ \end{array}$$

Máme tam veľa zátvoriek, poďme ich násobiť a celý výraz zjednodušiť:

$$\begin{array}{rl}& =2\times (2\times (2\times (2\times (2T(n-5)+2)+2)+2)+2)+2\\ & =2\times (2\times (2\times (2^{2}T(n-5)+2^2+2)+2)+2)+2\\ & =2\times (2\times (2^{3}T(n-5)+2^3+2^2+2)+2)+2\\ & =2\times (2^{4}T(n-5)+2^4+2^3+2^2+2)+2\\ & =2^{5}T(n-5)+2^5+2^4+2^3+2^2+2\\ \end{array}$$

Vidíme, že dvojky na seba postupne nabaľujú mocniny (pretože $2\times 2=2^2$ a $2^2\times 2=2^3$ a tak ďalej), pričom zakaždým násobíme každý prvok v zátvorke.

Rekurzia sa zastaví pri $T(0)=0$. Inými slovami, v poslednom riadku vyššie musíme zahrnúť triviálny prípad:

$$\begin{array}{rl}T(n)& =2^{n}T(\stackrel{0}{\overbrace{n-n}})+2^n+\cdots +2^4+2^3+2^2+2^1\\ & =\cancel{2^n\times 0}+2^n+\cdots +2^4+2^3+2^2+2^1\\ & =2^n+\cdots +2^4+2^3+2^2+2^1\\ \end{array}$$

Hneď sme aj všetky čísla 5 nahradili $n$. No a $2=2^1$. Výsledkom je geometrická postupnosť, kde prvým prvkom je $2^1$ a posledným prvkom je $2^n$ (ak exponenty vnímame odzadu, zoradené vzostupne).

Pri geometrickej postupnosti je dôležité určiť kvocient (označuje sa $q$ a vyjadruje pomer medzi dvomi za sebou idúcimi prvkami v postupnosti). Ak sa pozrieme na postupnosť vyššie, tak v podstate akýkoľvek prvok v postupnosti vieme zapísať ako $n$-násobok prvého člena v postupnosti. Kvocient $q=2$ – pretože násobíme medzi sebou dvojky, teda každý prvok je v postupnosti vzdialený 2-krát.

Všeobecný vzorec pre výpočet súčtu prvých $n$ členov geometrickej postupnosti:

$$S_n=a_1\times \frac{q^n-1}{q-1}$$

Ako prvý prvok ($a_1$) sme si zvolili $2^1$. Počet prvkov v tejto postupnosti je $n$ (pretože exponenty idú od 1 po $n$, a celá funkcia je iba táto geometrická postupnosť). Po dosadení dostávame funkciu:

$$\begin{array}{rl}T(n)& =2^1\times \frac{2^n-1}{2-1}\\ & =2\times \frac{2^n-1}{1}\\ & =2\times 2^n-1\\ T(n)& =2^{(n+1)}-1\\ \end{array}$$

Výsledok je teda $T(n)=2^{(n+1)}-1$.

Poďme na niečo iné (ale podobné):

$$\begin{array}{rl}T(1)& =2\\ T(n)& =5\times T(n-1)+1\\ \end{array}$$

Rozbalíme rekurziu:

$$\begin{array}{rl}T(n)& =5\times T(n-1)+1\\ & =5\times (\stackrel{T(n-1)}{\overbrace{5\times T(n-2)+1}})+1\\ & =5\times (\underset{T(n-1)}{\underbrace{5\times \stackrel{T(n-2)}{\overbrace{(5\times T(n-3)+1)}}+1}})+1\\ & \cdots \\ \end{array}$$

Podobne ako v predošlom prípade, je to postupnosť čísla 5, ktorá sa násobí:

$$\begin{array}{rl}& =5\times (5\times (5\times (5\times T(n-4)+1)+1)+1)+1\\ & =5\times (5\times (5\times (5\times (5\times T(n-5)+1)+1)+1)+1)+1\\ & \cdots \\ \end{array}$$

Výsledná postupnosť je geometrická:

$\begin{array}{rl}& =5^{5}T(n-5)+5^4+5^3+5^2+5^1+\stackrel{5^0=1}{\overbrace{1}}\\ \end{array}$

Doplníme triviálny prípad:

$\begin{array}{rl}T(n)& =5^{(n-1)}T(\stackrel{T(1)}{\overbrace{n-(n-1)}})+5^{(n-2)}+5^{(n-3)}+\cdots +5^4+5^3+5^2+5^1+\stackrel{5^0=1}{\overbrace{1}}\\ & =5^{(n-1)}T(\stackrel{T(1)}{\overbrace{n-(n-1)}})+5^{(n-2)}+5^{(n-3)}+\cdots +\stackrel{5^0=1}{\overbrace{5^{(n-n)}}}\\ & =2\times 5^{(n-1)}+\underset{\text{geometrická postupnosť:}\sum _{i=0}^{n-2}{5}^i}{\underbrace{(5^{(n-2)}+5^{(n-3)}+\cdots +1)}}\\ & =2\times 5^{(n-1)}+\frac{5^{(n-1)}-1}{5-1}\\ & =\frac{\stackrel{9\times 5^{(n-1)}}{\overbrace{8\times 5^{(n-1)}+5^{n-1}}}-1}{4}\\ T(n)& =\frac{9\times 5^{(n-1)}-1}{4}\\ \end{array}$

« Určovanie počtu operácií

Asymptotická notácia »