title: Metodo di Akra-Bazzi
text: # Metodo di Akra-Bazzi
  
  In informatica, il metodo Akra-Bazzi, o teorema Akra-Bazzi, è utilizzato per analizzare il comportamento asintotico delle ricorrenze matematiche che appaiono nello studio degli algoritmi divide et impera, in cui i diversi sottoproblemi hanno dimensioni decisamente differenti. È una generalizzazione del teorema principale, in cui si assume che i sottoproblemi abbiano invece dimensioni simili.
  
  ## La formula
  
  Il metodo Akra-Bazzi si applica alle formule ricorsive del tipo:
  
      $T(x)=g(x)+\sum _{i=1}^{k}a_{i}T(b_{i}x+h_{i}(x)),$
  
  per $x\geq x_{0}.$
  
  Le pre-condizioni sono:
  
  * vi sono sufficienti casi base;
  * $a_{i}$ e $b_{i}$ sono costanti per ogni $i;$
  * $a_{i}>0$ per ogni $i;$
  * $0<b_{i}<1$ per ogni $i;$
  * $\left|g'(x)\right|\in O(x^{c})$, dove $c$ è una costante e $O$ è la notazione O grande;
  * $\left|h_{i}(x)\right|\in O\left({\frac {x}{(\log x)^{2}}}\right)$ per ogni $i;$
  * $x_{0}$ è una costante.
  
  Il comportamento asintotico di $T(x)$ si trova determinando il valore di $p$ per cui $\sum _{i=1}^{k}a_{i}b_{i}^{p}=1$, sostituendolo poi nell'equazione
  
      $T(x)\in \Theta \left(x^{p}\left(1+\int _{1}^{x}{\frac {g(u)}{u^{p+1}}}du\right)\right)$
  
  (si veda Θ). Intuitivamente $h_{i}(x)$ rappresenta una perturbazione piccola nell'indice di $T.$ notando che
  
      $\lfloor b_{i}\rfloor =b_{i}x+(\lfloor b_{i}x\rfloor -b_{i}x)$
  
  e
  
      $\lfloor b_{i}x\rfloor -b_{i}x$
  
  sono sempre comprese tra 0 e 1, $h_{i}(x)$ può essere utilizzato per escludere la parte intera nell'indice, e lo stesso si può fare per la parte intera superiore.
  
  Quindi, $T(n)=n+T\left({\frac {1}{2}}n\right)$ e $T(n)=n+T\left(\left\lfloor {\frac {1}{2}}n\right\rfloor \right)$ avranno, ai fini del metodo Akra-Bazzi, lo stesso comportamento asintotico.
  
  ## Un esempio
  
  Sia
  
      $T(n)={\begin{cases}1,&{\text{se }}0\leq n\leq 3,\\n^{2}+{\frac {7}{4}}T\left(\left\lfloor {\frac {1}{2}}n\right\rfloor \right)+T\left(\left\lceil {\frac {3}{4}}n\right\rceil \right),&{\text{se }}n>3.\end{cases}}$
  
  Applicando il metodo, il primo passo consiste nel trovare il valore di $p$ per cui ${\frac {7}{4}}\left({\frac {1}{2}}\right)^{p}+\left({\frac {3}{4}}\right)^{p}=1$. Nell'esempio proposto, $p=2$. Usando quindi la formula, sia ha per il comportamento asintotico
  
      $T(x)\in \Theta \left(x^{p}\left(1+\int _{1}^{x}{\frac {g(u)}{u^{p+1}}}\,du\right)\right)=\Theta \left(x^{2}\left(1+\int _{1}^{x}{\frac {u^{2}}{u^{3}}}\,du\right)\right)=\Theta (x^{2}(1+\ln x))=\Theta (x^{2}\log x).$
  
  ## Impiego
  
  Il metodo Akra-Bazzi è più utile di molte altre tecniche in quanto copre un ventaglio molto ampio di casi. La sua principale applicazione è l'approssimazione del tempo di esecuzione di molti algoritmi divide et impera. Ad esempio nel merge sort, il numero di comparazioni richieste nel caso peggiore, che è all'incirca proporzionale al tempo di esecuzione, è dato ricorsivamente da $T(1)=0$ e
  
      $T(n)=T\left(\left\lfloor {\frac {1}{2}}n\right\rfloor \right)+T\left(\left\lceil {\frac {1}{2}}n\right\rceil \right)+n-1,$
  
  per gli $n>0$, e può essere valutato come $\Theta (n\log n)$.
  
  