notazione Theta

Secondo questa notazione, è un insieme di funzioni che rappresenta l’ordine di grandezza asintotico stretto (“uguale ordine di grandezza”) rispetto a quello del tempo impiegato dal processo, cioè $f(n)$ cresce allo stesso ritmo di $g(n)$.

${\lim }_{n\to \infty }\frac{f(n)}{g(n)}=k\in \mathbb{R}\to f(n)\in \Theta (g(n))$

Esempio: ${\lim }_{n\to \infty }\frac{3n}{2n}=\frac{3}{2}\to 3n\in \Theta (2n)$

N.B.: tutti i logaritmi hanno lo stesso tasso di crescita, quindi in queste notazioni si può tralasciare la base. ${\log }_{a}n\in \Theta (lo{g}_{b}n)$

N.B.: Se per una funzione $T(n)$, $T(n)\in O(n)\wedge T(n)\in \Omega (n)$, allora $T(n)\in \Theta (n)$