Master theorem

Anche chiamato teorema dell’esperto.

$$T(n)=\begin{array}{c}\{\begin{array}{ll}{c}_1& \text{mbox}sen=1\\ a\cdot T(\frac{n}{b})+c_2\cdot n^d& \text{mbox}altrimenti\end{array}\end{array}$$

con $a\in \mathbb{N}$

• $a\ge 1$
• $b>1$
• $c_1\ge 0$
• $c_2\ge 0$
• $d\ge 0$

title: Info
$\frac{n}b$ può stare sia per $\lfloor\frac{n}b\rfloor$ che per $\lceil\frac{n}b\rceil$

In questa equazione si hanno:

• $n$: dimensione del problema originario
• $a$: numero di sottoproblemi
• $\frac{n}{b}$: dimensione del sottoproblema
• $c_2\cdot n^d$: lavoro extra oltre le chiamate

title: Esempio
Ad esempio il binary search si può rappresentare in questo modo:
$$
T(n)=\begin{equation}\begin{cases}
c_1 & \mbox{se } n=1 \\
1 \cdot T(\frac{n}2)+c_2\cdot n^0 & \mbox{altrimenti}
\end{cases}\end{equation}
$$
 
Dove si ha $a=1, b=2 \mbox{ e } d=0$.

Se vale quanto sopra, si ha che

$$T(n)=\begin{array}{c}\{\begin{array}{ll}O(n^d)& \text{mbox}sed>{\log }_{b}a\\ O(n^{{\log }_{b}a}\log n)& \text{mbox}sed={\log }_{b}a\\ O(n^{{\log }_{b}a})& \text{mbox}sed<{\log }_{b}a\end{array}\end{array}$$

title: Esempio
Continuando l'esempio sopra della binary search, si ha che $a=1, b=2 \mbox{ e } d=0$, e quindi
$$
\log_ba=\log_21 = 0
$$
 
Essendo $d=\log_21=0$, si ha che la binary search $\in O(n^{\log_21}\log n)=O(\log n)$

title: Attenzione
Il teorema può essere usato solo quando la ricorsione è invocata su sottoproblemi che sono la frazione costante della dimensione originale, e i sottoproblemi devono avere tutti la stessa dimensione.

asd_10