Her ble man bedt om å løse rekurrensen \(T(n)=T(n/3)+\lg n\) og svare med \(\Theta\)-notasjon. Den kan lett løses med masterteoremet slik det er i pensum nå, men ikke slik det var den gang! Om man brukte det mer begrensede masterteoremet på rett måte, fikk man nesten full uttelling, men svaret blir like fullt ikke rett. Hvorfor ikke, og hvordan skulle man ha løst oppgaven?

Det sentrale her er at tilfelle 2 av det snevrere masterteoremet som ble brukt i tidligere utgaver av boka, hadde kravet $f(n)=\Theta(n^{\log_b a})$, uten faktoren $\lg^k n$, så det eneste plausible ville være å bruke tilfelle 3, som bare tilsynelatende fungerer.

Om vi prøver å bruke masterteoremet finner vi først at \(a=1\), \(b=3\) og \(\log_b a=0\). Det betyr at \(n^{\log_b a}=1\), og siden \(f(n)=\lg n\) har vi dermed

\[f(n) = \omega(n^{\log_b a}).\]

Vi ser altså at arbeidet \(f(n)\) i rotnoden av rekurrenstreet vokser større enn arbeidet \(n^{\log_b a}\) i løvnodene, og det kan se ut til at vi kan bruke tilfelle 3, og konkludere med at \(T(n)=\Theta(f(n))\), altså \(T(n)=\Theta(\lg n)\). Men det stemmer ikke! Det holder nemlig ikke at \(f(n)\) er asymptotisk større enn \(n^{\log_b a}\), som angitt av \(\omega\). Den må være større med en polynomisk faktor – vi må ha

\[f(n) = \Omega(n^{\log_b a + \epsilon}),\]

for en eller annen \(\epsilon > 0\). Og saken er: Enhver logaritme er asymptotisk mindre enn ethvert polynom – og dermed er \(\lg n\) ikke større enn \(1\) med en polynomisk faktor. Vi får ikke tilfelle 3 til å passe, samme hvilken \(\epsilon\) vi velger!

I stedet bruker vi arbeidshesten vår, og utvikler rekurrensen trinn for trinn, til vi får en rekke. I dette tilfellet (siden \(a=1\)) er det ganske lett å se hva rekken blir, men vi kan utvikle den i litt detalj, for sikkerhets skyld (der vi antar grunntilfelle $T(1) = 0$):

Denne summen følger direkte av rekurrensen. Siden vi deler \(n\) på \(3\) gjentatte ganger, til vi kommer til \(T(1)\), så er antall ledd i summen \(\log_3 n\). Vi bruker det faktum at \(\lg n/k = \lg n - \lg k\) for \(k=1\dots n\) og skriver om summen litt:

Vi kan bytte ut \(\lg n\) med \(\log_3 n\) uten at det får noe å si for det asymptotiske resultatet (det er bare en konstantfaktor \(\log_3(2)\) i forskjell):

\[T(n) = \Theta\bigl(\, \log_3^2 n - (0 + 1 + 2 + 3 + \cdots + \log_3 n) \,\bigr)\]

Vi kan bruke det faktum at \(1 + 2 + 3 + \cdots + k = k(k+1)/2\), og ser at

\[0 + 1 + 2 + 3 + \cdots + \log_3 n = \frac{\log_3 n\cdot(\log_3 n + 1)}{2} = \frac{\log_3^2 n}{2} + \frac{\log_3 n}{2}\]

Med andre ord:

\[T(n) = \Theta\left( \log_3^2 n - \frac{\log_3^2 n}{2} - \frac{\log_3 n}{2} \right) = \Theta\bigl(\log_3^2 n\bigr) = \Theta(\lg^2 n)\]

Naturligvis trenger man ikke gå så grundig til verks her – oppgaven spør ikke om utregning. Mye av det som er regnet ut trinnvis over kunne man ha skissert kjapt i hodet, og evt. sjekket svaret med substitusjonsmetoden etterpå.