ALGEBRA DELLA NOTAZIONE ASINTOTICA :
1A per ogni k > 0 e per ogni f(n) > 0 , se f(n) è un O(g(n)) allora lo è anche k(n)
questa regola vale anche per la funzione omega e teta , in poche parole stiamo dicendo che le costanti moltiplicative le possiamo ignorare
REGOLA SULLA COMMUTAZIONE SULLA SOMMA:
2A per ogni f(n),d(n) > 0 , se f(n) è un O(g(n)) e d(n) è un O(h(n)) allora f(n) + d(n) è un O(g(n) + h(n)) = O (max(g(n),h(n)))
informalmente possiamo dire che le notazioni asintotiche commutano con l'operazione di somma
REGOLA SULLA COMMUTAZIONE DEL PRODOTTO:
3A per ogni f(n) , d(n) > 0 , se f(n) è un O(g(n)) e d(n) è un O(h(n)) allora f(n)d(n) è un O(g(n)h(n))
informalmente si può dire che le notazioni asintotiche commutano con l'operazione di prodotto