Да бисмо могла да се анализира сложеност програма потребно је владати одређеним математичким апаратом. У наставку ћемо резимирати основне математичке појмове које ћемо користити у анализи сложености алгоритама.
Подсетимо се математичких својстава елементарних функција.
Природа функција у математици лакше се проучава и разуме када су дати њихови графици. У зависности од релевантних величина улазних вредности или од вредности функција (вредности функција могу давати број инструкција или време извршавања), некад је погодно за приказ функција уместо уобичајеног Декартовог система користити неку модификовану верзију. На пример, можемо бирати различите распоне \(x\) и \(y\) координата које ће бити приказане на графику (у случају да је распон неке од координата много већи од оне друге, однос јединичних подеока се подешава тако да график и даље задржи скоро квадратни облик). Друго, једна од оса (па и обе) може бити логаритамски трансформисана — тада се од једне до друге истакнуте тачке скале не долази сабирањем са одређеном константом (\(1\) у уобичајеном Декартовом систему), већ множењем са одређеном константом (на пример, \(2\) или \(10\)). На слици 6 приказани су графици функција које се јављају често у анализи сложености.
Са свих графика јасно је уочљив релативни однос брзина раста ових функција. Неспорно је да међу приказаним функцијама експоненцијална функција расте најбрже, да је наредна по брзини раста функција \(n^2\), затим \(n \log{n}\), потом \(n\) и на крају \(\log{n}\) која расте јако споро. Са друге стране, може се приметити да се закључци о међусобном односу брзина раста морају изводити веома пажљиво, јер могу бити различити у зависности од одабраног распона \(x\) и \(y\) координата. На пример, на првом графику и \(x\) и \(y\) су одабрани тако да иду до 1000, а на другом је одабрано да \(x\) иде до 1000, а \(y\) до 100000. Са првог графика се може стећи утисак да је функција \(n \log{n}\) по брзини раста негде тачно између \(n\) и \(n^2\), док се са другог већ тај однос може прецизније проценити и види се да функција \(n^2\) расте много брже него \(n\log{n}\) и \(n\). Први приказани график заправо је само мали део другог (добија се тако што се \(y\) оса “сасече” при самом дну, на вредности 1000). Стога приликом анализе алгоритама графици треба да се подесе тако да \(x\)-оса показује димензије улаза заиста релевантне за проблем који се решава, а да се на \(y\) оси приказује реална процена броја инструкција тј. времена извршавања које се у реалном контексту допуштају алгоритму. Ако приказане функције мере број инструкција, онда је други график (у том смислу) много бољи од првог, јер се на првом не приказују извршавања након 1000 инструкција, што је за данашње рачунаре занемариво мало. Можемо рећи да би се још бољи график добио када би се број инструкција повећао на милионе, па чак и милијарде, јер су данашњи рачунари у стању да изврше милијарде инструкција у неколико секунди. Графици са logаритамским скалама много боље могу да представе функције и њихове односе, али треба стећи добар осећај за то како их треба читати.
Током анализе алгоритама често имамо потребу да израчунамо одређене коначне суме. Резимирајмо их кроз неколико најзначајнијих примера.
Гаусу се приписује да је још као дете израчунао да је
\[1 + 2 + \ldots + n = \sum_{k=0}^{n} k = \frac{n(n+1)}{2}.\]
Ако је \(n\) паран број, у овом збиру се крије \(n/2\) парова чији је збир \(n+1\): први и последњи, други и претпоследњи, итд. У истом духу, ако означимо тражени збир са \(S\), онда је \(2S = S+S = (1 + 2 + \ldots + n) + (n + (n-1) + \ldots + 1) = n\cdot(n+1)\).
Некада слика говори више од речи (видети слику 7).
На основу претходног, једноставно се изводи да је збир првих \(n\) чланова аритметичког низа чији је први члан \(a\), а разлика између свака два суседна члана једнака \(r\) једнака
\[a + (a + r) + (a + 2r) + \ldots + (a + (n-1)\cdot r) = \sum_{k=0}^{n-1} (a + k\cdot r) = n\cdot a + r\frac{n(n-1)}{2}.\]
Интуиција нам опет говори да се овде крије \(\frac{n}{2}\) парова (ако је \(n\) паран) чији је збир \(a_0 + a_{n-1}\), што опет доводи до формуле \(\frac{n}{2}\left(2a + (n-1)\cdot r\right)\).
Један важан аритметички низ је низ непарних бројева. Важи да је \(1 + 3 + 5 + \ldots + (2k-1) = \frac{k}{2} \cdot (1 + (2k-1)) = k^2\).
Израчунавање збира узастопних парних бројева се лако своди на збир узастопних бројева. \(2 + 4 + 6 + \ldots 2k = 2(1+2+3+\ldots k) = k(k+1)\).
Поново слика говори више од речи (видети слику 8).
Изведимо формулу за збир првих \(n\) чланова геометријског низа коме је први члан \(a\) а количник свака два узастопна члана \(q \neq 1\). Обележимо тражену суму са \(S\).
\[S = a + a \cdot q^1 + a \cdot q^2+ \ldots + a \cdot q^{n-2} + a \cdot q^{n-1} = \sum_{k=0}^{n-1} a\cdot q^k.\]
Ако леву и десну страну претходне једнакости помножимо са \(1 - q\) добијамо једнакост:
\(S \cdot (1 - q) = a \cdot (1 - q) + a \cdot q \cdot (1 - q) + a \cdot q^2 \cdot (1 - q) + \ldots + a \cdot q^{n-2}\cdot (1 - q) + a \cdot q^{n-1} \cdot (1 - q)\)
Извршимо множења на десној страни једнакости:
\[S \cdot (1 - q) = a - a\cdot q + a \cdot q - a \cdot q^2 + a \cdot q^2 - a \cdot q^3 + \ldots + a \cdot q^{n-2} - a \cdot q^{n-1} + a \cdot q^{n-1} - a \cdot q^n\]
Сређивањем последњег израза добијамо \(S \cdot (1 - q) = a - a \cdot q^n\). Према томе, пошто је \(q \neq 1\), важи
\[S = a \cdot \frac {1 - q^n}{1 - q}.\]
За \(|q| < 1\) геометријски ред конвергира и сума му је \(\frac{a}{1-q}\).
Нама ће често бити корисни случајеви \(q=2\) и \(q=1/2\).
На основу претходне формуле, за \(a=1\) и \(q=2\), важи да је \(1+2+\ldots+2^{n-1} = 2^n - 1\). Ова формула има интересантно тумачење. Сума са леве стране представља укупан број чворова на првих \(n\) нивоа потпуног бинарног дрвета (видети слику 9), док је израз са десне стране за један мањи од броја чворова на наредном нивоу \(n+1\). Дакле, на сваком наредном нивоу бинарног дрвета има један чвор више него што је чворова на свим претходним нивоима дрвета.
За \(a=1\) и \(q=1/2\) добијамо да је
\[1+1/2+\ldots+(1/2)^{n-1} = \frac{1-(1/2)^n}{1-1/2} = 2-(1/2)^{n-1}.\]
Са порастом \(n\) ова вредност се приближава вредности \(2\) (свакако је њоме ограничена одозго).
Опет слика говори више од речи (видети слику 10).
Прикажимо како можемо израчунати суму квадрата свих природних бројева од \(1\) до \(n\). Важи да је
\[(k+1)^3 - k^3 = k^3 + 3k^2 + 3k + 1 - k^3 = 3k^2 + 3k + 1.\]
Зато је \[\begin{eqnarray*} 2^3 - 1^3 &=& 3\cdot 1^2 + 3\cdot 1 + 1\\ 3^3 - 2^3 &=& 3\cdot 2^2 + 3\cdot 2 + 1\\ \ldots\\ (n+1)^3 - n^3 &=& 3\cdot n^2 + 3\cdot n + 1 \end{eqnarray*}\]
Сабирањем претходних једнакости добијамо
\[(n+1)^3 - 1 = 3\cdot(1^2+\ldots + n^2) + 3\cdot(1+\ldots+n) + (1+\ldots + 1)\]
тј. \[3\cdot \sum_{k=1}^{n} k^2 = (n+1)^3-1 - 3\sum_{k=1}^{n} k - \sum_{k=1}^{n} 1.\]
На основу раније изведених формула за збир аритметичког низа, следи да је
\[\begin{eqnarray*} \sum_{k=1}^n k^2 &=& \frac{1}{3}\cdot\left(n^3 +3n^2 +3n - 3\frac{n(n+1)}{2} - n\right)\\ &=& \frac{n\cdot (2n+1)\cdot (n+1)}{6}\\ &=& \frac{1}{3}\left(n \cdot (n + \frac{1}{2}) \cdot (n+1)\right). \end{eqnarray*}\]
Дакле, сума квадрата природних бројева од \(1\) до \(n\) се асимптотски понаша као \(\frac{n^3}{3}\).
Опет слика говори више од речи (видети слику 11).
Потпуно аналогно, сумирањем израза \((k+1)^4 - k^4\) од \(1\) до \(n\) и применом до сада изведених формула може се показати да је
\[1^3+2^3+\ldots + n^3 = \sum_{k=1}^n k^3 = \frac{(n(n+1))^2}{4}.\]
Ово тврђење, познато као Никомахова теорема показује да је збир кубова свих природних бројева од \(1\) до \(n\) једнак квадрату збира свих природних бројева од \(1\) до \(n\) и асимптотски се понаша као \(\frac{n^4}{4}\).
Опет слика говори више од речи (видети слику 12).
Пошто ће нас у анализи алгоритама најчешће занимати само асимптотско понашање функција, најважније је запамтити да се сума \(n\) \(p\)-тих степена свих природних бројева од \(1\) до \(n\) асимптотски понаша као \(\frac{n^{p+1}}{p+1}\).
Проценимо асимптотско понашање суме логаритама \(\log{1} + \log{2} + \ldots + \log{n}\).
Пошто је логаритам растућа функција, сваки од \(n\) чланова овог збира ограничен је одозго вредношћу \(\log{n}\). Зато важи да овај збир припада класи \(O(n \log{n})\). Докажимо да ово ограничење није превише грубо. Важи да је
\[\log{1} + \log{2} + \ldots + \log{n} \geq \log{(n/2)} + \log{(n/2 + 1)} + \ldots + \log{n},\]
јер је првих \(n/2\) чланова који су из суме изостављени сигурно ненегативно. Пошто је логаритам растућа функција (за основу већу од \(1\)), сви сабирци у овом збиру су већи или једнаки \(\log{(n/2)}\), па је
\[\log{(n/2)} + \log{(n/2 + 1)} + \ldots + \log{n} \geq \log{(n/2)} + \log{(n/2)} + \ldots + \log{(n/2)}.\]
Збир на десној страни има \(n/2\) истих сабирака и једнак је \((n/2)\cdot \log{(n/2)}\). Стога је почетни збир логаритама ограничен и одоздо и одозго функцијама које су \(\Theta({n\log{n}})\), па је и сам \(\Theta({n\log{n}})\).
Још један начин да се ово покаже који се често среће у литератури је следећи. Збир логаритама, једнак је логаритму производа, па заправо овде рачунамо вредност \(\log{1\cdot\ldots\cdot n} = \log{n!}\). По Стирлинговој формули \(n!\) се понаша као \(\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\). Зато се \(\log{n!}\) понаша као \(n\log n - n + O(\log{n})\), па је укупан збир \(\Theta(n\log{n})\).
Покушајмо да уопштимо неколико претходних резултата. Често се асимптотска оцена сложености своди на израчунавање неког збира \(T(n) = c + f(1) + f(2) + \ldots + f(n)\), тако да се одређивање асимптотског понашања своди на сумирање.
Збир \(n\) сабирака реда \(1+2+\ldots+n\) има вредност \(n(n+1)/2\), која је реда \(\Theta(n^2)\). То је само дупло мање од вредности збира \(n + \ldots + n\), који се састоји од \(n\) сабирака и има вредност \(n^2\).
Збир \(n\) сабирака \(\log{1} + \ldots + \log{n}\) има вредност која се понаша као \(n\log{n} - n\), што је асимптотски исто као вредност збира \(\log{n} + \ldots + \log{n}\) који има \(n\) сабирака и вредност \(n\log{n}\).
Слично, збир \(1^2 + \ldots + n^2\) има вредност \(n(n+1)(2n+1)/6\), што је \(\Theta(n^3)\) и само је око три пута мање од збира \(n^2 + \ldots + n^2\) који има \(n\) сабирака и вредност \(n^3\).
Иако овакве генерализације прете да буду непрецизне, са малом дозом резерве се може проценити да алгоритми у којима се \(n\) пута примењује нека операција сложености \(\Theta(f(k))\) имају сложеност \(\Theta(n\cdot f(n))\), чак и када се операција у сваком кораку примењује над подацима који су се за \(O(1)\) повећали у односу на претходни корак и само у крајњој инстанци имамо \(\Theta(n)\) података.
За израчунавање и оцену сума могу се користити и изводи и интеграли. Приметимо да је неодређени интеграл функције \(x^p\) функција \(\frac{x^{p+1}}{p+1}\), а да се збир \(p\)-тих степена свих природних бројева од \(1\) до \(n\) асимптотски понаша управо као \(\frac{n^{p+1}}{p+1}\). То није случајност. Размотримо монотоно растућу функцију \(f\) (таква је функција \(f(x)=x^n\)) на домену \(x \geq 0\). Сума \(\sum_{k=0}^{n-1} f(k)\) се може представити као површина \(n\) правоугаоника (свакоме је ширина \(1\), а висина \(k\)-тог је \(f(k)\)). На слици је приказана сума првих \(25\) потпуних квадрата. Са слике је види да је та сума (збир површина правоугаоника) блиска површини испод криве \(f(x) = x^2\) која се може израчунати (тј. чије се асимптотско понашање може проценити) применом одређених интеграла.
Илуструјмо ово и мало прецизније. Површина испод криве \(f(x)\) за \(k \leq x \leq k+1\) једнака је одређеном интегралу \(\int_{k}^{k+1} f(x)\ dx\). Пошто је функција растућа, та површина је већа од површине правоугаоника чија је висина \(f(k)\) и ширина \(1\), а мања од површине правоугаоника чија је висина \(f(k+1)\) и ширина \(1\) тј. важи
\[f(k) \leq \int_k^{k+1} f(x)\ dx \leq f(k+1).\]
Зато је
\[\sum_{k=0}^{n-1} f(k) \leq \int_0^{n} f(x)\ dx \leq \sum_{k=0}^{n-1} f(k+1).\]
Горњу границу суме можемо директно прочитати из прве неједнакости. Пошто је
\[\sum_{k=0}^{n-1} f(k+1) = \sum_{k=0}^{n-1} f(k) - f(0) + f(n),\]
из друге неједнакости следи и доња граница, па важи:
\[\int_{0}^n f(x)\ dx + f(0) - f(n) \leq \sum_{k=0}^{n-1} f(k) \leq \int_0^n f(x)\ dx.\]
Случај када је \(f(x)\) монотоно опадајућа функција за \(x \geq 0\) се обрађује аналогно (само је потребно уместо \(\leq\) користити \(\geq\)).
На пример, понашање суме \(\sum_{k=0}^{n-1} ka^k = a + 2a^2 + 3a^3 + \ldots + (n-1)a^{n-1},\) можемо проценити израчунавањем одређеног интеграла \(\int_0^n xa^x\ dx.\)
Он се једноставно може израчунати парцијалном интеграцијом за \(u=x\) (па је \(du=dx\)) и \(dv=a^x\ dx\), одакле је \(v = \frac{a^x}{\ln{a}}\). Зато је
\[\int_0^n xa^x\ dx = \int_0^n u\ dv = (uv)\big\rvert_0^n - \int_{0}^n v\ du = \frac{na^n}{\ln{a}} - \frac{\int_0^n a^x\ dx}{\ln{a}} = \frac{na^n}{\ln{a}} - \frac{(a^n - 1)}{\ln^2{a}},\]
па се ова функција асимптотски понаша као \(na^n\).
Ову суму је могуће израчунати и егзактно, применом диференцирања. Наиме, важи да је
\[\sum_{k=0}^{n-1} x^k = 1 + x + \ldots + x^{n-1} = \frac{x^n - 1}{x-1}.\]
Диференцирањем обе стране по \(x\) добијамо
\[1 + 2x + 3x^2 + \ldots + (n-1)x^{n-2} = \frac{nx^{n-1}(x-1) - (x^n-1)}{(x-1)^2}.\]
Множењем са \(x\) добијамо
\[\sum_{k=0}^{n-1} kx^k = x + 2x^2 + 3x^3 + \ldots + (n-1)x^{n-1} = x\frac{nx^{n-1}(x-1) - (x^n-1)}{(x-1)^2}.\]
На пример, за \(x=2\) добијамо да је \(\sum_{k=0}^{n-1} k2^k = (n-2)\cdot 2^{n} + 2\).
Напоменимо и да се та сума веома једноставно може израчунати и сасвим елементарним техникама. Нека је \(S_x(n) = \sum_{k=0}^{n-1} kx^k\). Тада множењем ове једнакости са \(x\), одузимањем добијеног резултата од полазне једнакости и применом формуле за збир геометријског низа добијамо
\[\begin{eqnarray*} S_x(n) &=& x^1 + 2x^2 + 3x^3 + \ldots + (n-2)x^{n-2} + (n-1)x^{n-1}\\ x\cdot S_x(n) &=& x^2 + 2x^3 + 3x^4 + \ldots + (n-2)x^{n-1} + (n-1)x^n\\ S_x(n) - xS_x(n) &=& x^1 + x^2 + x^3 + \ldots + x^{n-1} + (n-1)x^n\\ (1 - x)S_x(n) &=& x(x^0 + \ldots + x^{n-2}) + (n-1)x^n = x\frac{1-x^{n-1}}{1-x} + (n-1)x^n \end{eqnarray*}\]
Одатле следи да је
\[S_x(n) = \frac{x-x^n}{(1-x)^2} + (n-1)x^n\]
Лако се показује да су добијени изрази и израз добијен применом диференцирања једнаки. Заменом вредности \(x=2\) поново добијамо да је \(S_2(n) = \sum_{k=0}^{n-1} k2^k = (n-2)\cdot 2^{n} + 2\).
Размотримо збир \(H(n) = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots + \frac{1}{n}\). Овај збир можемо елегантно а прилично добро приближно проценити.
Прво покажимо да \(H(n)\) тежи бесконачности како \(n\) тежи бесконачности. Важи да је \(H(n) > 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{4} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \ldots\) Наиме, важи да је \(\frac{1}{3} > \frac{1}{4}\), затим да је \(\frac{1}{5} > \frac{1}{8}\), \(\frac{1}{6} > \frac{1}{8}\) и \(\frac{1}{7} > \frac{1}{8}\) итд. Међутим, важи да је \(\frac{1}{4} + \frac{1}{4} = \frac{1}{2}\), да је \(\frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8} = \frac{1}{2}\) итд. Зато је десни збир једнак \(1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} + \ldots\), а овај збир јасно дивергира тј. тежи бесконачности са повећањем броја сабирака.
Слично би се могло доказати и коришћењем процене суме одређеним интегралом. Број \(H(n)\) се може проценити као \(\int_1^{n+1} \frac{1}{x}\mathrm{d}x\), који је једнак \((\ln{x})\big\rvert^{n+1}_1\) тј. \(\ln{(n+1)}\).
На графику функције \(H(n)\) може се уочити да она веома споро тежи бесконачности и може се приметити веома сличан облик графику функције \(\ln{n}\). Заиста, доказује се да разлика између функција \(H(n)\) и \(\ln{n}\) веома брзо конвергира и тежи константи \(\gamma\) која је позната под именом Ојлер-Маскеронијева константа и чија је вредност приближно једнака \(\gamma = 0.57722\). Ништа се не би променило и да се посматра однос \(H(n)\) са функцијом \(\ln{(n+1)}\) (јер са повећањем \(n\) разлика између \(\ln{(n+1)}\) и \(\ln{n}\) веома брзо тежи нули), осим што би процена била мало прецизнија за мале вредности \(n\).
Kod rekurzivnih funkcija, vreme \(T(n)\) potrebno za izračunavanje vrednosti funkcije za ulaz veličine \(n\) može se izraziti kao zbir vremena izračunavanja za sve rekurzivne pozive i vremena potrebnog za pripremu rekurzivnih poziva i objedinjavanje rezultata. Tako se, obično jednostavno, može zapisati linearna rekurentna relacija oblika:
\[T(n) = a_1 T(n-1) + \ldots + a_k T(n-k) + r(n), \;\;\; n \geq k,\]
gde rekurzivna funkcija za ulaz veličine \(n\) vrši po nekoliko (\(a_i\) su prirodni brojevi) rekurzivnih poziva za ulaze veličina \(n-1\), , \(n-k\), dok je \(r(n)\) vreme potrebno za pripremu poziva i objedinjavanje rezultata. Ovakvom rekurentnom vezom i početnim članovima niza \(T(0)\), \(T(1)\), \(\ldots\), \(T(k-1)\) u potpunosti je određen niz \(T\).
U nekim slučajevima, iz rekurentne relacije i početnih elemenata može se eksplicitno izračunati nepoznati opšti član niza \(T(n)\). U nekim slučajevima eksplicitno rešavanje jednačine nije moguće, ali se može izračunati asimptotsko ponašanje niza \(T(n)\).
Наведимо неколико најчешћих облика примене рекурентних једначина на анализу рекурзивних алгоритама.
У првој групи се проблем своди на проблем димензије која је тачно за један мања од димензије полазног проблема.
У другој групи се проблем своди на два (или више) проблема чија је димензија за један или два мања од димензије полазног проблема. То обично доводи до експоненцијалне сложености.
У наредној групи се проблем своди на један (или више) потпроблема који су значајно мање димензије од полазног (обично су бар дупло мањи). Ово доводи до полиномијалне сложености, па често и до веома ефикасних решења.
Ако су границе у самим једначинама егзактне, скоро у свим претходно набројаним једначинама дато решење није само горње ограничење, већ је асимптотски егзактно. На пример, решење једначине \(T(n) = 2T(n/2) + \Theta(n)\), \(T(1) = \Theta(1)\) има решење \(T(n) = \Theta(n\log{n})\). Изузетак је пример Фибоначијевог низа где понашање јесте експоненцијално, али основа није \(2\), већ златни пресек \((1 + \sqrt{5}) / 2\).
Размотримо једначину облика
\[T(n) = aT(n-1),\]
за \(n > 0\), при чему је дата вредност \(T(0) = c\). Једноставно се показује да је решење ове једначине геометријски низ \(T(n)= ca^n\).
Ово решење говори да је сложеност рекурзивне функције за параметар \(n\) која врши више од једног рекурзивног позива димензије \(n-1\), чак и када се остале операције занемаре, експоненцијална (на пример, ако је \(T(n) = 2T(n-1)\), онда \(T(n)\) припада класи \(O(2^n)\)). Зато таква решења треба избегавати када год је то могуће.
Размотримо једначину облика
\[T(n)=aT(n-1)+bT(n-2),\]
за \(n > 1\), при чему су дате вредности за \(T(0)=c_0\) и \(T(1)=c_1\).
Уколико нису наведени почетни услови, једначина има више решења. Заиста, уколико низови \(T_1(n)\) и \(T_2(n)\) задовољавају једначину, тада једначину задовољава и њихова произвољна линеарна комбинација \(T(n)=\alpha T_1(n) + \beta T_2(n)\):
\[\begin{eqnarray*} T(n) &=& \alpha T_1(n) + \beta T_2(n)\\ &=& \alpha(aT_1(n-1)+bT_1(n-2)) + \beta(aT_2(n-1)+bT_2(n-2)) \\ &=& a(\alpha T_1(n-1) + \beta T_2(n-1)) + b (\alpha T_1(n-2) + \beta T_2(n-2))\\ &=& aT(n-1)+bT(n-2)\;. \end{eqnarray*}\]
С обзиром на то да и нула низ (низ чији су сви елементи нуле) тривијално задовољава једначину, скуп решења чини векторски простор.
Размотримо функције облика \(t^n\) и покушајмо да проверимо да ли постоји број \(t\) такав да \(t^n\) буде решење дате једначине. За такву вредност би важило:
\[t^n=a\cdot t^{n-1}+b \cdot t^{n-2},\]
односно, после множења са \(t^2\) и дељења са \(t^n\):
\[t^2=at+b.\]
Дакле, да би \(t^n\) било решење једначине, потребно је да \(t\) буде корен наведене квадратне једначине, која се назива карактеристична једначина за хомогену рекурентну једначину другог реда.
Ако су \(t_1\) и \(t_2\) различити корени ове једначине (они могу бити и комплексне вредности), може се доказати да опште решење \(T(n)\) може бити изражено као линеарна комбинација базних функција \(t_1^n\) и \(t_2^n\), тј. да је облика
\[T(n)=\alpha \cdot t_1^n + \beta \cdot t_2^n \;,\]
тј. да ове две функције чине базу поменутог векторског простора решења. Ако се жели пронаћи оно решење које задовољава задате почетне услове (тј. задовољава дате вредности \(T(0)=c_0\) и \(T(1)=c_1\)), онда се вредности коефицијената \(\alpha\) и \(\beta\) могу добити решавањем система добијеног за \(n=0\) и \(n=1\), тј. решавањем система једначина \(c_0=\alpha + \beta\), \(c_1 = \alpha \cdot t_1 + \beta \cdot t_2\).
У случају да је \(t_1\) двоструко решење карактеристичне једначине, може се доказати да опште решење \(T(n)\) може бити изражено као линеарна комбинација базних функција \(t_1^n\) и \(n\cdot t_1^n\), тј. да је облика
\[T(n)=\alpha \cdot t_1^n + \beta \cdot n \cdot t_1^n \;.\]
Коефицијенти \(\alpha\) и \(\beta\) који одређују партикуларно решење које задовољава почетне услове, такође се добијају решавањем система за \(n=0\) и \(n=1\).
Из претходног следи да је сложеност рекурзивних функција које доводе до рекурентних једначина другог реда експоненцијална, па је често довољно одредити основу те експонецијалне функције (решавањем карактеристичне једначине), док се одређивање конкретних вредности коефицијената \(\alpha\) и \(\beta\) мање значајно. Такве рекурзивне функције је добро избегавати и решења формулисати, уколико је могуће, тако да им сложеност буде полиномска (добар пример како се ово може урадити чини Фибоначијев низ). Постоје, међутим, и рекурзивни алгоритми експоненцијалне сложености који решавају проблеме за које се не зна да ли имају решења полиномске сложености.
Пример 2.A.1. Нека за време извршавања \(T(n)\) алгоритма \(A\) (где \(n\) одређује улазну вредност за алгоритам) важи \(T(n+2)=2T(n+1)+3T(n)\) (за \(n\geq 1\)) и \(T(1)=5, T(2)=19\). Сложеност алгоритма \(A\) може се израчунати на следећи начин. Карактеристична једначина за наведену хомогену рекурентну везу је
\[t^2=2t+3,\]
и њени корени су \(t_1=3\) и \(t_2=-1\). Општи члан низа \(T(n)\) може бити изражен у облику
\[T(n)=\alpha \cdot t_1^n + \beta \cdot t_2^n \;.\]
тј. \[T(n)=\alpha \cdot 3^n + \beta \cdot (-1)^n \;.\]
Из \(T(1)=5, T(2)=19\) добија се систем:
\[\begin{eqnarray*} \alpha \cdot 3+\beta \cdot (-1) &=& 5\\ \alpha \cdot 9+\beta \cdot 1 &=& 19 \end{eqnarray*}\]
чије је решење \((\alpha,\beta)=(2,1)\), па је \(T(n)=2 \cdot 3^n+(-1)^n\), одакле следи да је \(T(n)=O(3^n)\).
Приметимо да је за рачунање асимптотске сложености било довољно израчунати корене карактеристичне једначине. Већи од њих је \(3\) и то је довољно да се закључи да сложеност припада класи \(O(3^n)\).
Пример 2.A.2. Нека за време извршавања \(T(n)\) алгоритма \(A\) (где \(n\) одређује улазну вредност за алгоритам) важи \(T(n+2)=4T(n+1)-4 T(n)\) (за \(n\geq 1\)) и \(T(1)=6, T(2)=20\). Сложеност алгоритма \(A\) може се израчунати на следећи начин. Карактеристична једначина за наведену хомогену рекурентну везу је
\[t^2=4t-r\]
и њен двоструки корен је \(t_1=2\). Општи члан низа \(T(n)\) може бити изражен у облику
\[T(n)=\alpha \cdot 2^n + \beta \cdot n \cdot 2^n \;.\]
Из \(T(1)=6, T(2)=20\) добија се систем
\[\begin{eqnarray*} \alpha \cdot 2+\beta \cdot 2 &=& 6\\ \alpha \cdot 4+\beta \cdot 8 &=& 20 \end{eqnarray*}\]
чије је решење \((\alpha,\beta)=(1,2)\), па је \(T(n)=2^n+2 \cdot n \cdot 2^n\), одакле следи да је \(T(n)=O(n 2^n)\).
У овом примеру се у рекурентној једначини јавља и један негативан коефицијент (коефицијент \(-4\) уз вредност \(T(n)\)) али, како смо видели, то не утиче на општи начин решавања. Иако се једначине са негативним коефицијентима не могу јавити директним моделовањем рекурзивних функција (јер се у њима укупно време добија сабирањем времена које се утроши на сваки рекурзивни позив), оне могу настати током процеса решавања и увођењем разних смена у оригиналне једначине.
Хомогена рекурентна једначина реда \(k\) (где \(k\) може да буде и веће од \(2\)) је једначина облика:
\[T(n)=a_1 \cdot T(n-1)+a_2 \cdot T(n-2) + \ldots + a_k \cdot T(n-k),\]
за \(n > k-1\), при чему су дате вредности за \(T(0)=c_0\), \(T(1)=c_1\), \(\ldots\), \(T(k-1)=c_{k-1}\).
Технике приказане на хомогеној једначини другог реда, лако се уопштавају на једначину произвољног реда \(k\). Карактеристична једначина наведене једначине је:
\[t^k=a_1 \cdot t^{k-1}+a_2 \cdot t^{k-2} + \ldots + a_k.\]
Ако су решења \(t_1\), \(t_2\), \(\ldots\), \(t_k\) сва различита, онда је опште решење полазне једначине облика:
\[T(n)=\alpha_1 \cdot t_1^n+\alpha_2 \cdot t_2^n + \ldots + \alpha_k \cdot t_k^n,\]
при чему се коефицијенти \(\alpha_i\) могу добити из почетних услова (када се у наведено опште решење за \(n\) уврсте вредности \(0\), \(1\), \(\ldots\), \(k-1\)).
Уколико је неко решење \(t_1\) двоструко, онда у општем решењу фигуришу базне функције \(t_1^n\) и \(n \cdot t_1^n\). Уколико је неко решење \(t_1\) троструко, онда у општем решењу фигуришу базне функције \(t_1^n\), \(n \cdot t_1^n\), \(n^2 \cdot t_1^n\), итд.
Размотримо једначину облика
\[T(n) = aT(n-1) + b,\]
за \(n > 0\), при чему је дата вредност \(T(0) = c\). Један начин решавања овог типа једначина је свођење на хомогену једначину другог реда. Из \(T(1) = aT(0) + b,\) следи да је \(T(1)=ac+b\). Из
\[T(n) = aT(n-1) + b\]
\(T(n+1) = aT(n) + b\),
следи \(T(n+1)-T(n) = (aT(n) + b)-(aT(n-1) + b)=aT(n)-aT(n-1)\) и, даље, \(T(n+1)=(a+1)T(n)-aT(n-1)\), за \(n>0\). Решење новодобијене хомогене једначине се може добити на горе описани начин (јер су познате и почетне вредности \(T(0) = c\) и \(T(1) = ac+b\)).
Пример 2.A.3.
Размотримо нехомогену рекурентну једначина првог реда \(T(0)=0\) и \(T(n)=2T(n-1)+1\) (и \(T(1)=2T(0)+1=1\) (ова једначина се добија када се анализира број пребацивања дискова у игри Ханојске куле). Из \(T(n)-2T(n-1)=1=T(n-1)-2T(n-2)\) (за \(n>1\)) следи \(T(n)=3T(n-1)-2T(n-2)\). Ова једначина је хомогена једначина другог реда и она може бити решена на раније описан начин. Карактеристична једначина је \(t^2=3t-2\) и њени корени су \(2\) и \(1\). Из система
\[\begin{eqnarray*} \alpha \cdot 1 +\beta \cdot 1 &=& 0\\ \alpha \cdot 2 +\beta \cdot 1 &=& 1 \end{eqnarray*}\]
следи \(\alpha=1\) и \(\beta=-1\), па је
\[T(n)=1 \cdot 2^n + (-1) \cdot 1^n = 2^n - 1 \;.\]
Нехомогена рекурентна једначина реда \(k\) (\(k>0\)) облика:
\[T(n)=a_1 \cdot T(n-1)+a_2 \cdot T(n-2) + \ldots + a_k \cdot T(n-k)+c,\]
за \(n > k-1\), при чему су дате вредности за \(T(0)=c_0\), \(T(1)=c_1\), \(\ldots\), \(T(k-1)=c_{k-1}\), може се решити свођењем на хомогену рекурентну једначину реда \(k+1\), аналогно горе описаном случају за \(k=1\).
Пример 2.A.4. Размотримо једначину \(T(0)=T(1)=c_1\), где је \(c_1\) нека константа и \(T(n)=T(n-1)+T(n-2)+c_2\), где је \(c_2\) нека константа (ова једначина се добија приликом анализе сложености израчунавања елемената Фибоначијевог низа). Из \(T(n)=T(n-1)+T(n-2)+c_2\) и \(T(n+1)=T(n)+T(n-1)+c_2\), следи \(T(n+1)=2T(n)-T(n-2)\). Карактеристична једначина ове једначине је \(t^3=2t^2-1\) и њени корени су \(1\), \(\frac{1+\sqrt{5}}{2}\) и \(\frac{1-\sqrt{5}}{2}\), па је опште решење облика
\(T(n)=a\cdot 1^n + b \cdot \left(\frac{1+\sqrt{5}}{2}\right)^n + c \cdot \left(\frac{1-\sqrt{5}}{2}\right)^n,\)
одакле следи да је \(T(n)=O(\left(\frac{1+\sqrt{5}}{2}\right)^n)\).
Ова једначина се јавља, на пример, код рекурзивног одређивања збира серије бројева, одређивања минимума/максимума, линеарне претраге и слично.
Једначина је довољно једноставна да би се решила одмотавањем. Прецизности ради, представимо је у облику \(T(n) = T(n-1) + c\) и \(T(0) = d\), након одмотавања добијамо да важи:
\[\begin{eqnarray*} T(n) &=& T(n-1) + c\\ &=& T(n-2) + c + c\\ &=& T(n-3) + c + c + c\\ &=& \ldots \\ &=& T(0) + n \cdot c \\ &=& d + n \cdot c\\ &=& O(n). \end{eqnarray*}\]
Ова једначина се јавља, на пример, код наивних алгоритама сортирања низа, попут сортирања селекцијом или сортирања уметањем. На пример, код сортирања селекцијом се проналази позиција најмањег елемента у низу (за шта је потребно \(O(n)\) корака), он се доводи на првом место у низу и затим се прелази на сортирање остатка низа, који садржи \(n-1\) елемената.
Код једначине \(T(n) = T(n-1) + O(n)\), \(T(0) = O(1)\) слично добијамо \(n\) сабирака који су сви \(O(n)\) тако да је укупна сума \(O(n^2)\). Поставља се питање да ли је ова граница егзактна тј. да ли је могуће да је сложеност мања од изведеног горњег ограничења. Претпоставимо да је \(T(n) = T(n-1) + cn\) и да је \(T(0) = d\). Тада је
\[\begin{eqnarray*} T(n) &=& T(n-1) + cn \\ &=& T(n-2) + c(n-1) + cn \\ &=& \ldots\\ &=& T(0) + c(1 + \ldots + n)\\ &=& d + cn(n+1)/2, \end{eqnarray*}\]
тако да је \(T(n) = \Theta(n^2)\).
Покажимо још и шта се дешава са једначином \(T(n) = T(n-1) + c\log{n}\), \(T(0) = d\). Одмотавањем добијамо
\[\begin{eqnarray*} T(n) &=& T(n-1) + c\log{n}\\ &=& T(n-2) + c\log{(n-1)} + c\log(n)\\ &=& \ldots \\ &=& d + c(\log{1} + \ldots + \log{n}). \end{eqnarray*}\]
Раније смо показали да се збир логаритама понаша као \(\Theta(n\log{n})\), па је то и решење ове једначине.
Једначине у којима се рекурзивни позиви димензије \(n-1\) понављају више пута имају експоненцијална решења.
У питању је нехомогена једначина првог реда и она се може решити свођењем на хомогену једначину. Претпоставимо да је једначина \(T(n) = 2T(n-1)+c\), \(T(0)=d\). Важи \(T(n+1) = 2T(n)+c\), па је \(T(n+1) - T(n) = 2T(n) - T(n-1)\), тј. \(T(n+1) = 3T(n) - 2T(n-1)\). Карактеристична једначина је \(t^2=3t-2\), чија су решења \(t=2\) и \(t=1\). Опште решење је, дакле, облика \(T(n) = \alpha 2^n + \beta\). Важи и \(T(0) = d\) и \(T(1)=2T(0)+c=2d+c\), одакле се могу израчунати и конкретне вредности коефицијената \(\alpha\) и \(\beta\), јер је \(\alpha + \beta = d\) и \(2\alpha + beta = 2d+c\), па је \(\alpha = d+c\), а \(\beta = -c\), тј. решење је \((c+d)2^n - c\).
Ова једначина се још једноставније може решити одмодавањем.
\[\begin{eqnarray*} T(n) &=& 2T(n-1) + c\\ &=& 2(2T(n-2) + c) + c = 4T(n-2) + 2c + c\\ &=& 4(2T(n-3)+c) + 2c + c\\ &=& 8T(n-3) + 4c + 2c + c\\ &=& \ldots\\ &=& 2^nT(0) + (2^{n-1} + \ldots + 2 + 1)\cdot c\\ &=& 2^n\cdot d + (2^n-1)\cdot c = O(2^n). \end{eqnarray*}\]
Дакле, иако се у сваком рекурзивном позиву ради мало посла, рекурзивних позива има експоненцијално много, што доводи до изразито неефикасног алгоритма.
Функције које задовољавају једначину \(T(n) = 2T(n-1) + O(n)\), \(T(0) = O(1)\) такође показују експоненцијалну сложеност.
Одмотавањем једначине \(T(n) = 2T(n-1) + c\cdot n\), \(T(0) = d\) добијамо
\[\begin{eqnarray*} T(n) &=& 2T(n-1) + c\cdot n\\ &=& 2(2T(n-2) + c\cdot (n-1)) + c\cdot n = 4T(n-2) + c\cdot (2 (n-1) + n)\\ &=& 4(2T(n-3)+ c\cdot (n-2)) + c\cdot (2 (n-1) + n)\\ &=& 8T(n-3) + c\cdot(4(n-2) + 2(n-1) + n)\\ &=& \ldots\\ &=& 2^nT(0) + c(2^{n-1}\cdot 1 + 2^{n-2}\cdot 2 + \ldots + 2(n-1) + n)\cdot O(1)\\ &=& 2^n\cdot d + c(\sum_{k=0}^{n}2^k(n-k)). \end{eqnarray*}\]
Коришћењем раније изведених формула можемо једноставно израчунати и суму
\[\sum_{k=0}^{n} 2^{k}(n-k) = n + 2(n-1) + 2^2(n-2) + \ldots + 2^{n-1}\cdot 1.\]
Важи да је
\[\begin{eqnarray*} \sum_{k=0}^{n} 2^{k}(n-k) &=& n\sum_{k=0}^{n}2^k - \sum_{k=0}^{n}k2^k\\ &=& n(2^{n+1}-1) - ((n-1)2^{n+1}+2)\\ &=& 2^{n+1}-n-2 \end{eqnarray*}\]
Зато је \(T(n) = 2^n\cdot d + c(2^{n+1}-n-2)\). Дакле, и у овом случају функција показује експоненцијално понашање \(O(2^n)\).
Једначине засноване на декомпозицији проблема на неколико мањих потпроблема које су облика \(T(n) = aT(n/b) + O(n^k)\), \(T(0) = O(1)\) се решавају на основу мастер теореме.
Теорема: Решење рекурентне релације \(T(n) = aT(n/b)+cn^k\), где су \(a\) и \(b\) целобројне константе такве да важи \(a \geq 1\) и \(b \geq 1\), и \(c\) и \(k\) су позитивне реалне константе је
\[T(n)=\left\{ \begin{array}{ll} \Theta(n^{\log_b a}) \;,\; & \mbox{ако је} \log_b{a}>k, \mbox{тј.} a > b^k\\ \Theta(n^k \log n) \;,\; & \mbox{ако је} \log_b{a}=k, \mbox{тј.} a = b^k \\ \Theta(n^k) \;,\; & \mbox{ако је} \log_b{a}<k, \mbox{тј.} a < b^k \end{array} \right.\]
Пре него што дамо доказ ове теореме, покушајмо да кроз низ примера дамо интуитивно објашњење зашто ова теорема важи, у сва три своја случаја.
У првом случају се добија дрво рекурзивних позива чији број чворова доминира послом који се ради у сваком чвору. Размотримо, на пример, једначину \(T(n) = 2\cdot T(n/2) + O(1)\), \(T(1) = O(1)\). Дрво ће садржати \(O(n)\) чворова, а у сваком чвору ће се вршити посао који захтева \(O(1)\) операција. Одмотавањем рекурентне једначине, добијамо
\[\begin{eqnarray*} T(n) &=& 2\cdot T(n/2) + O(1)\\ &=& 4\cdot T(n/4) + 2\cdot O(1) + O(1)\\ &=& 8\cdot T(n/8) + 4\cdot O(1) + 2 \cdot O(1) + O(1)\\ &=& 2^k \cdot T(n/2^k) + (2^{k-1} + \ldots + 2 + 1)\cdot O(1). \end{eqnarray*}\]
Ако је \(n=2^k\) добијамо да је \(n/2^k = 1\), па пошто је на основу формуле за збир геометријског низа \(2^{k-1} + \ldots + 2 + 1 = 2^k - 1\), сложеност је \(\Theta({n})\). И када \(n\) није степен двојке, добија се исто асимптотско понашање (што се може доказати ограничавањем одозго и одоздо степенима двојке).
У другом случају су број чворова и посао који се ради на неки начин уравнотежени. Размотримо, на пример, једначину \(T(n) = 2\cdot T(n/2) + c\cdot n\), \(T(1) = O(1)\) и поново покушајмо да је одмотамо.
\[\begin{eqnarray*} T(n) &=& 2\cdot T(n/2) + c\cdot n\\ &=& 2\cdot(2\cdot T(n/4) + c\cdot n/2) + c\cdot n\\ &=& 4T(n/4) + c\cdot n + c\cdot n\\ &=& 4(2T(n/8) + c\cdot n/4) + 2\cdot c\cdot n\\ &=& 8T(n/8) + 3\cdot c\cdot n\\ &=& \ldots\\ &=& 2^k\cdot T(n/2^k) + k\cdot c\cdot n. \end{eqnarray*}\]
Ако је \(n=2^k\) после \(k = \log_2{n}\) корака \(n/2^k\) ће достићи вредност \(1\) тако да ће збир бити реда величине \(n\cdot O(1) + \log_2{n}\cdot c\cdot n = \Theta(n\log{n})\). Исто важи и када \(n\) није степен двојке.
У трећем случају посао који се ради у чворовима доминира бројем чворова. Размотримо једначину \(T(n) = T(n/2) + cn\), \(T(1) = O(1)\). Њеним одмотавањем добијамо да је
\[\begin{eqnarray*} T(n) &=& T(n/2) + cn\\ &=& T(n/4) + cn/2 + cn\\ &=& T(n/8) + cn/4 + cn/2 + cn\\ &=& \ldots\\ &=& T(n/2^k) + cn(1/2^{k-1} + \ldots + 1/2 + 1). \end{eqnarray*}\]
Поново, ако је \(n=2^k\), тада је први члан једнак \(O(1)\) и пошто је на основу формуле за збир геометријског низа \(1/2^{k-1} + \ldots + 1/2 + 1 = (1 - (1/2)^k)/(1-(1/2)) = 2 - 2/n\) збир је једнак \(O(1) + cn(2-2/n) = \Theta(n)\).
Претпоставимо, једноставности ради, да је \(n=b^s\) (ово значи да ће се на неком нивоу рекурзије доћи до тога да су сви позиви за \(n=1\), тј. да ће након \(s\) рекурзивних позива у свима њима доћи до излаза из рекурзије, јер је \(n/b^s = 1\)). Размотајмо једначину, уопштавајући је на облик: \(T(n)=aT(n/b) + f(n)\), \(T(1) = d\):
\[\begin{eqnarray*} T(n) &=& aT\left(\frac{n}{b}\right) + f(n)\\ &=& a\left(aT\left(\frac{n}{b^2}\right) + f\left(\frac{n}{b}\right)\right) + f(n) = a^2T\left(\frac{n}{b^2}\right) + \left(af\left(\frac{n}{b}\right) + f(n)\right) = \\ \ldots\\ &=& a^sT\left(\frac{n}{b^s}\right) + \left(a^{s-1}f\left(\frac{n}{b^{s-1}}\right) + \ldots + af\left(\frac{n}{b}\right) + f(n)\right) \\ &=& a^sT(1) + \left(a^{s-1}f\left(\frac{n}{b^{s-1}}\right) + \ldots + af\left(\frac{n}{b}\right) + f(n)\right) \end{eqnarray*}\]
Приметимо да решење зависи од два сабирка. Вредност \(a^s\) је број листова дрвета рекурзивних позива, а \(a^s\cdot T(1)\) је време које се утроши на обраду базних случајева тј. обраду излазака из рекурзије. Други сабирак даје укупно време потребно за припрему свих рекурзивних позива и обраду њихових резултата. На првом нивоу постоји један позив у ком се обрађује улаз димензије \(n\) (вредност \(f(n)\)), на другом \(a\) позива у ком се обрађују улази димензије \(n/b\) (вредност \(af(n/b)\)), на трећем \(a^2\) позива у ком се обрађују улази димензије \(n/b^2\) (вредност \(a^2f(n/b^2)\)) и тако даље. Постоји тачно \(s\) нивоа рекурзије (на последњем је излаз из рекурзије).
Из \(n = b^s\), следи да је \(s=\log_b{n}\), па важи следеће:
\[a^s = a^{\log_b{n}} = a^\frac{\log_a n}{\log_a b} = a^{\log_a n \cdot \log_b a} = \left(a^{\log_a n}\right)^{\log_b a} = n^{\log_b{a}}.\]
Зато под претпоставком да излаз из рекурзије захтева константно време, за први сабирак важи \(a^s\cdot T(1) = \Theta\left(n^{\log_b{a}}\right)\). У зависности од функције \(f\) и односа вредности \(a\) и \(b\), зависи да ли ће временом доминирати први или други сабирак. Наиме, вредност \(\log_b{a}\) се назива критична вредност и резултат зависи од тога да ли други сабирак има асимптотску сложеност мању, већу или једнаку од \(n^{\log_b{a}}\).
У случају полазне једначине \(T(n) = aT(n/b) + cn^k\), \(T(1) = d\), важи да је \(f(n) = cn^k\), па добијамо:
\[T(n) = d\cdot a^s + c\cdot n^k \cdot \left(1 + \frac{a}{b^k} + \ldots + \left(\frac{a}{b^k}\right)^{s-1}\right)\]
Ако је \(a \neq b^k\), тада је други сабирак могуће упростити применом формуле за збир геометријског низа.
\[T(n) = d\cdot a^s + c\cdot n^k\cdot \left(\frac{\left(\frac{a}{b^k}\right)^s - 1}{\frac{a}{b^k}-1}\right).\]
Случај \(a < b^k\)
Ако је \(a < b^k\), тада члан \(\left(\frac{a}{b^k}\right)^s\) тежи нули са порастом \(n\) тј. \(s\), па је збир геометријског низа одозго ограничен вредношћу \(\frac{1}{1 - \frac{a}{b^k}} = \Theta(1)\). Зато је асимптотско понашање времена извршавања једнако \(T(n) = \Theta(n^{\log_b{a}}) + \Theta(n^k)\). Пошто је \(a < b^k\), важи и да је \(\log_b{a} < k\), па је \(a^s = n^{\log_b{a}} = O(n^k)\) и коначно асимптотско понашање решења је \(\Theta(n^k)\).
Приметимо да је у овом случају рекурзивни поступак такав да је посла у листовима (приликом изласка из рекурзије) мање него што има посла на припреми рекурзивних позива и обради њихових резултата. Ово се обично дешава код слабо разгранатих дрвета и код дрвета код којих је припрема рекурзивних позива и обрада добијених резултата скупа операција.
Случај \(a > b^k\)
У овом случају вредност геометријског низа тежи бесконачности, брзином водећег сабирка \(\Theta\left(\left(\frac{a}{b^k}\right)^s\right)\). Зато важи
\[\begin{eqnarray*} T(n) &=& d\cdot a^s + c\cdot n^k\cdot \left(\frac{\left(\frac{a}{b^k}\right)^s - 1}{\frac{a}{b^k}-1}\right)\\ &=& \Theta(a^s) + c\cdot n^k \cdot \Theta\left(\left(\frac{a}{b^k}\right)^s\right)\\ &=& \Theta(a^s) + c\cdot n^k \cdot \Theta\left(\frac{a^s}{(b^s)^k}\right)\\ &=& \Theta(n^{\log_b a}) + c\cdot n^k\cdot \Theta\left(\frac{n^{\log_b{a}}}{n^k}\right)\\ &=& \Theta(n^{\log_b a}) + \Theta(n^{\log_b{a}}) = \Theta(n^{\log_b{a}}). \end{eqnarray*}\]
Примећујемо да у овом случају доминирају листови дрвета, тј. време потребно за припрему свих рекурзивних позива и обраду резултата је асимптотски једнако времену које се потроши у листовима тј. при изласку из рекурзије. Ово се обично дешава код веома разгранатих дрвета, код којих је припрема рекурзивних позива и обрада резултата брза.
Случај \(a = b^k\)
У овом случају не можемо применити формулу за збир геометријског низа, међутим, сваки његов члан је једнак 1. Зато је \(T(n) = d\cdot a^s + c\cdot n^k\cdot s\). Важи да је \(c \cdot n^k\cdot s = c\cdot \log_b n \cdot n^k = \Theta(n^k \log n)\). Пошто је и сада \(a^s = n^{\log_b a} = n^k\), укупно време је \(T(n) = \Theta(n^k\log{n})\).
Приметимо да је у овом случају време потрошено на сваком нивоу рекурзије (укључујући и излаз из рекурзије) уједначено и једнако \(\Theta(n^k) = \Theta\left(n^{\log_b a}\right)\). Укупан број нивоа рекурзије је \(s = \Theta(\log n)\).
Прокоментаришимо да се у неким проблемима добијају једначине које нису баш у сваком рекурзивном позиву идентичне овим наведеним. На пример, приликом анализе алгоритма QuickSort, ако је пивот тачно на средини низа, важи да је \(T(n) = 2T(n/2) + O(n)\) и \(T(1) = O(1)\). Када би се то стално догађало, решење би било \(T(n) = O(n\log{n})\), међутим, вероватноћа да се то догоди је страшно мала, јер у већини случајева пивот не дели низ на два дела потпуно исте димензије и зато треба бити обазрив. Ако би се десило да пивот стално завршавао на једном крају низа, једначина би била \(T(n) = T(n-1) + O(n)\), \(T(1) = O(1)\), што би довело до сложености \(O(n^2)\), што и јесте сложеност најгорег случаја. Анализом коју ћемо приказати касније се може утврдити да је просечна сложеност \(O(n\log{n})\) тј. да иако пивот није стално на средини, да је у довољном проценту случајева негде близу ње (рецимо између 25% и 75% дужине низа). Слична анализа важи и за проблем проналажења медијане.
Међутим, постоје и алгоритми код којих ствари стоје другачије. Приликом обиласка бинарног дрвета, балансираност нема утицаја. Наиме, ако је дрво потпуно, тада је једначина \(T(n) = 2T(n/2) + O(1)\), \(T(1) = O(1)\), чије је решење \(O(n)\). Међутим, чак и када је дрво издегенерисано у листу, једначина је \(T(n) = T(n-1) + O(1)\), \(T(1) = O(1)\), чије је решење опет \(O(n)\). Какав год да је однос броја чворова у левом и десном поддрвету решење ће бити \(O(n)\). То се може описати једначином \(T(n) = T(k) + T(n-k-1) + O(1)\), \(T(1) = O(1)\), за \(0 \leq k \leq n-1\), чије ће решење бити \(O(n)\), без обзира на то какво се \(k\) појављује у разним рекурзивним позивима.