Jeg prøver å løse rekurrensen $T(n) = 16T(n/4) + n!$ med masterteoremet. Dette gir jo $a = 16$, $b = 4$ og $\log_b(a) = 2$. Men når $f(n)=n!$, hvordan kan jeg finne ut om det er av tilfelle 1, 2 eller 3? Dersom det hadde stått f.eks. $n^2$, så har vi $c = 2$ og det ville vært tilfelle 2. Hva gjør jeg når det er fakultet involvert i $f(n)$?

Basert på Piazza-spørsmål fra 2013

Du har alt funnet ut at $\log_b a=2$, som jo er en viktig start. Det betyr altså at $n^{\log_b a}=n^2$. Denne skal du så sammenligne med f(n)=n!. Da har du altså de tre mulighetene fra masterteoremet:

  1. Er $n!=O(n^{2-\epsilon})$ for en eller annen $\epsilon >0$?
  2. Er $n!=\Theta(n^2)$?
  3. Er $n!=\Omega(n^{2+\epsilon})$ for en eller annen $\epsilon>0$?

Merk: I nyere utgave av læreboka dekker tilfelle 2 også faktorer av typen $\log^k n$.

Litt enklere sagt: Asymptotisk sett, vokser $n!$ strengt langsommere enn $n^2$, like raskt, eller strengt raskere? Ut fra hva du kommer frem til her ender du da opp med enten at $T(n)=\Theta(n^2)$ (alternativ 1), $T(n)=\Theta(n^2\lg n)$ (alternativ 2) eller $T(n)=\Theta(n!)$.

Kanskje du tar oppgaven videre herfra, eller er det fortsatt uklart?

Forøvrig: For det siste alternativet kreves også at $2((n/2)!)\leq c⋅(n!)$ for en eller annen konstant $c>1$. Det er ikke så vanskelig å vise at det er tilfelle, men om du vet at masterteoremet kan brukes på rekurrensen din, så trenger du jo egentlig ikke slåss med denne biten, siden kun ett av alternativene er aktuelt uansett. Men det kan jo være nyttig trening det òg.

$n!$ vokser raskere enn $n^2$, så da er det vel tilfelle 3?

Det stemmer!