Per semplificare il calcolo del costo computazionale asintotico degli algoritmi si possono sfruttare delle semplici regole.
Regole sulle costanti moltiplicative
- 1A: se è un allora anche è un
- 1B: se è un allora anche è un
- 1C: se è un allora anche è un
In generale, le costanti moltiplicative si possono ignorare
Regole sulla commutatività con la somma
Per ogni
- 2A: se è un e è un allora è un
- 2B: se è un e è un allora è un
- 3B: se è un e è un allora è un
In generale, le notazioni asintotiche commutano con la somma.
Regole sulla commutatività con il prodotto
Per ogni
- 3A: se è un e è un allora è un
- 3B: se è un e è un allora è un
- 3C: se è un e è un allora è un
In generale, le notazioni asintotiche commutano con la moltiplicazione.
Dimostrazioni
