Ordine di grandezza

Possiamo aumentare il livello di astrazione considerando solo l’ordine di grandezza:

• consideriamo solo il termine “dominante”
• ignoriamo del tutto le costanti

Limiti superiori

<aside> 💡 $0 \leq T(n)$ è $O(f(n))$ se esistono due costanti $c>0$ ed $n_0 \geq 0$ tali che $\forall n \geq n_0$ si ha $T(n) \leq c \cdot f(n)$

</aside>

Limiti inferiori

<aside> 💡 $T(n)$ è $\Omega(f(n))$ se esistono due costanti $c>0$ ed $n_0 \geq 0$ tali che $\forall n \geq n_0$ si ha $T(n) \geq c \cdot f(n) \geq 0$

</aside>

Limiti esatti

<aside> 💡 $T(n)$ è $\Theta(f(n))$ se è sia $O(f(n))$ che $\Omega(f(n))$

</aside>

Affermazione

Ogni algoritmo basato sui confronti richiede almeno $\Omega(nlogn)$ confronti

Proprietà

• transitività
  • se $f = O(g)$ e $g = O(h)$ allora $f = O(h)$
  • se $f = \Omega(g)$ e $g = \Omega(h)$ allora $f = \Omega(h)$
  • se $f = \Theta(g)$ e $g = \Theta(h)$ allora $f = \Theta(h)$
• additività
  • se $f = O(h)$ e $g = O(h)$ allora $f + g= O(h)$
  • se $f = \Omega(h)$ e $g = \Omega(h)$ allora $f + g= \Omega(h)$
  • se $f = \Theta(h)$ e $g = \Theta(h)$ allora $f + g= \Theta(h)$

Bound asintotici per alcune funzioni di uso comune

• polinomi: $a_0+a_1n+..+a_dn^d$ con $a_d>0$ è $\Theta(n^d)$
• logaritmi:
  • $\Theta(log_an)=\Theta (log_bn)$ $\forall a,b >0$
  • $logn=O(n)$
• tempo lineare $O(n)$: il tempo di esecuzione è al più un fattore costante per la dimensione dell’input
  • esempi: computazione del massimo $\Omega(n)$, merge (combinare 2 sequenze ordinate in una lista ordinata) $O(n+m)$
• tempo quadratico $O(n^2)$: tipicamente si ha quando un algoritmo esamina tutte le coppie di elementi input
  • esempio: coppia di punti più vicina