Her ble man bedt om å løse rekurrensen og svare med -notasjon. Det ligner jo forlokkende på den typen rekurrenser vi kan løse med masterteoremet – men dessverre passer den ikke helt! Om man brukte masterteoremet på rett måte, fikk man nesten full uttelling, men svaret blir like fullt ikke rett. Hvorfor ikke, og hvordan skal man løse oppgaven?

Om vi prøver å bruke masterteoremet finner vi først at , og . Det betyr at , og siden har vi dermed

Vi ser altså at arbeidet i rotnoden av rekurrenstreet vokser større enn arbeidet i løvnodene, og det kan se ut til at vi kan bruke tilfelle 3, og konkludere med at , altså . Men det stemmer ikke! Det holder nemlig ikke at er asymptotisk større enn , som angitt av . Den må være større med en polynomisk faktor – vi må ha

for en eller annen . Og saken er: Enhver logaritme er asymptotisk mindre enn ethvert polynom – og dermed er ikke større enn med en polynomisk faktor. Vi får ikke tilfelle 3 til å passe, samme hvilken 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 ) er det ganske lett å se hva rekken blir, men vi kan utvikle den i litt detalj, for sikkerhets skyld:

Denne summen følger direkte av rekurrensen. Siden vi deler gjentatte ganger, til vi kommer til , så er antall ledd i summen . Vi bruker det faktum av for og skriver om summen litt:

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

Vi kan bruke det faktum at , og ser at

Med andre ord:

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å.