Per prima cosa, valgono le seguenti proprietà/definizioni:
- \( f = O( g ) \) se e solo se \(\displaystyle \forall k > 0,\,\exists n_0,\,\forall n > n_0,\; \lvert f(n)\rvert \le \lvert kg(n) \rvert \);
- \( f = \Omega( g ) \) se e solo se \( g = O( f ) \);
- \( f = \Theta( g ) \) se e solo se \( f = O( g ) \wedge f = \Omega( g ) \);
Nota inoltre che sarebbe più appropriato scrivere \( f \in O( g ) \) piuttosto che \( f = O( g ) \), dato che \(O(n)\) è di fatto un sottoinsieme dell'insieme delle funzioni.
Detto questo, la relazione \(f \preceq g \Leftrightarrow f = O( g )\) è una relazione di ordine (insomma è riflessiva, antisimmetrica e transitiva), così come la relazione \(f \succeq g \Leftrightarrow f = \Omega( g )\). Invece, la relazione \(f \sim g \Leftrightarrow f = \Theta( g )\) è una relazione di equivalenza (riflessiva, simmetrica e transitiva).
Usando la proprietà transitiva è evidente che \(f = \Omega( \Omega( g ) ) \Rightarrow f = \Omega( g )\), \(f = \Theta( \Theta( g ) ) \Rightarrow f = \Theta( g )\), \(f = O( O( g ) ) \Rightarrow f = O( g )\). Inoltre, siccome \(f = \Theta( g ) \Rightarrow f = \Omega( g )\) e \(f = \Theta( g ) \Rightarrow f = O( g )\), si ricava facilmente che \(f = \Omega( \Theta( g ) ) \Rightarrow f = \Omega( g )\) e \(f = O( \Theta( g ) ) \Rightarrow f = O( g )\). Similmente, si può osservare che \(f = \Theta( \Omega( g ) ) \Rightarrow f = \Omega( g )\) e \(f = \Theta( O( g ) ) \Rightarrow f = O( g )\).
Gli insiemi \(\Omega( O(n) )\) e \(O( \Omega(n) )\)
non sono ben definiti e non vanno
mai usati.