Teorema dell'esperto

Lemma

La somma ${\displaystyle s(n)=\sum _{i=0}^{\log _{b}n}a^{i}f\left({\frac {n}{b^{i}}}\right)}$ definita su potenze di ${\displaystyle b}$, dove ${\displaystyle a\geq 1}$ e ${\displaystyle b>1}$ sono costanti e ${\displaystyle f}$ è non negativa, ha rispettivamente comportamento asintotico:

1. sotto l'ipotesi del caso 1 del teorema principale, ${\displaystyle s(n)=\Theta \left(n^{\log _{b}a}\right)}$;
2. sotto l'ipotesi del caso 2 del teorema principale, ${\displaystyle s(n)=\Theta \left(n^{\log _{b}a}\log bn\right)}$;
3. sotto l'ipotesi del caso 3 del teorema principale, se esistono una costante ${\displaystyle 0<c<1}$ e un intero ${\displaystyle n_{0}}$ tali che ${\displaystyle \forall n\geq n_{0}\colon af\left({\frac {n}{b}}\right)\leq cf(n)}$, allora ${\displaystyle s(n)=\Theta \left(f(n)\right)}$.

Dimostrazione

Dimostrazione del teorema principale

Nel caso particolare in cui ${\displaystyle T}$ sia definita solo su potenze esatte di ${\displaystyle b}$, analizzando l'albero della ricorsione relativo alla relazione di ricorrenza si osserva che

${\displaystyle T(n)=\sum _{i=0}^{\log _{b}n}a^{i}f\left({\frac {n}{b^{i}}}\right)+\Theta \left(n^{\log _{b}a}\right).}$

Applicando quindi il lemma dimostrato precedentemente, si ottiene immediatamente la validità del teorema principale nel caso particolare in cui ${\displaystyle n}$ sia definita su potenze di ${\displaystyle b}$. Questo ovviamente non è sufficiente a dimostrare il teorema, ma può essere esteso al caso generale considerando il caso in cui compaiano parti intere superiori o inferiori.

Nel caso di una parte intera superiore, nel considerare l'albero di ricorsione alla chiamata ${\displaystyle i}$-esima l'argomento assume la forma

${\displaystyle n_{i}={\begin{cases}n,\quad &i=0,\\\lceil {\frac {n_{i-1}}{b}}\rceil ,&i>0.\end{cases}}}$

Poiché dalla definizione di parte intera superiore si ha ${\displaystyle \lceil x\rceil \leq x+1}$, si ottiene

${\displaystyle n_{i}\leq {\frac {n}{b^{i}}}+\sum _{i=0}^{i-1}{\frac {1}{b^{i}}}<{\frac {n}{b^{i}}}+{\frac {b}{b-1}}.}$

Da ciò si osserva che ${\displaystyle n_{\lfloor \log _{b}n\rfloor }=O(1)}$, quindi alla profondità di ricorsione ${\displaystyle \lfloor \log _{b}n\rfloor }$ il costo del problema è limitato da una costante. Si generalizza quindi la prima equazione per ${\displaystyle n}$ arbitrario, non più ristretto alle potenze di ${\displaystyle b}$

${\displaystyle T(n)=\sum _{i=0}^{\lfloor \log _{b}n\rfloor }a^{i}f\left(n_{i}\right)+\Theta \left(n^{\log _{b}a}\right)}$

e si può procedere a studiare la somma. Il terzo caso procede in maniera esattamente analoga al terzo caso del lemma. Per il secondo caso, dalla definizione di O-grande e ricordando l'espressione di ${\displaystyle n_{i}}$ si ha che esiste una costante ${\displaystyle c>0}$ e un intero ${\displaystyle n_{0}}$ tali che, per ${\displaystyle n\geq n_{0}}$

${\displaystyle f\left(n_{i}\right)\leq c\left({\frac {n}{b^{i}}}+{\frac {b}{b-1}}\right)^{\log _{b}a}\leq c\left({\frac {n^{\log _{b}a}}{a^{i}}}\right)\left(1+{\frac {b}{b-1}}\right)^{\log _{b}a}=O\left({\frac {n^{\log _{b}a}}{a^{i}}}\right).}$

Il limite asintotico ottenuto permette di procedere poi in maniera analoga al caso 2 del lemma. Per il primo caso, in maniera analoga a quanto appena fatto si mostra che

${\displaystyle f\left(n_{i}\right)=O\left(\left({\frac {n}{b^{i}}}\right)^{\log _{b}a-\varepsilon }\right)}$

che permette di procedere poi in maniera analoga al caso 1 del lemma. Questo completa la dimostrazione del teorema principale in caso di parte intera superiore, nel caso della parte intera inferiore la dimostrazione è analoga.

Caso 1

Sia data la seguente relazione di ricorrenza:

${\displaystyle T_{A}(n)=9\,T_{A}\left({\frac {n}{3}}\right)+n.}$

Si ha ${\displaystyle a=9}$, ${\displaystyle b=3}$ e ${\displaystyle f(n)=n}$. Allora ${\displaystyle n^{\log _{b}a}=n^{\log _{3}9}=\Theta \left(n^{2}\right).}$ Dato che ${\displaystyle f(n)=O\left(n^{\log _{3}9-\varepsilon }\right)}$ quando ${\displaystyle \varepsilon =1}$, è possibile applicare il caso 1 del teorema dell'esperto ottenendo la soluzione

${\displaystyle T_{A}(n)=\Theta \left(n^{2}\right).}$

Caso 2

Sia data ora la relazione di ricorrenza:

${\displaystyle T_{A}(n)=T_{A}\left({\frac {2\,n}{3}}\right)+1,}$

in cui ${\displaystyle a=1}$, ${\displaystyle b=3/2}$ e ${\displaystyle f(n)=1}$. Essendo ${\displaystyle n^{\log _{b}a}=n^{\log _{3/2}1}=\Theta (n^{0})=\Theta (1)}$ ed ${\displaystyle f(n)=1}$, vale il caso 2 del teorema dell'esperto, che porta alla soluzione ${\displaystyle T_{A}(n)=\Theta (\log n).}$

Caso 3

Infine sia data la relazione di ricorrenza:

${\displaystyle T_{A}(n)=3\,T_{A}\left({\frac {n}{4}}\right)+n\log n,}$

in cui ${\displaystyle a=3}$, ${\displaystyle b=4}$ e ${\displaystyle f(n)=n\log n}$. Essendo ${\displaystyle n^{\log _{b}a}=n^{\log _{4}3}=O\left(n^{0,793}\right)}$ ed ${\displaystyle f(n)=\Omega \left(n^{\log _{4}3+\varepsilon }\right)}$, in cui ${\displaystyle \varepsilon \approx 0,2}$, il caso 3 del teorema dell'esperto si può applicare solo se vale la condizione di regolarità per ${\displaystyle f(n)}$. Per ${\displaystyle n}$ sufficientemente grande si ha ${\displaystyle 3\left({\frac {n}{4}}\right)\log \left({\frac {n}{4}}\right)\leq \left({\frac {3}{4}}n\log n\right)=cf(n)}$ per ${\displaystyle c=3/4\leq 1}$. Di conseguenza la soluzione della ricorrenza è ${\displaystyle T_{A}(n)=\Theta (n\log n).}$