Dowód złożoności obliczeniowej

[MichalMix]

Jak formalnie przedstawić dowód, że dla algorytmów \(\displaystyle{ f \left(x \right)}\) i \(\displaystyle{ g \left(x \right)}\) o złożoności obliczeniowej \(\displaystyle{ O \left(n ^{k} \right)}\) \(\displaystyle{ f \left(x\right) \cdot g \left(x \right) => O ft( n^{2 k} \right)}\) ?

[Dumel]

\(\displaystyle{ f(n)=O(n^k)}\) więc istnieje pewna stala \(\displaystyle{ M}\) spelniajaca dla dostatecznie duzych wartosci n: \(\displaystyle{ |f(n)| n^k}\) więc:
\(\displaystyle{ |f(n) g(n)| < M_1 n^k M_2 n^k n^{2k}}\)
czyli
\(\displaystyle{ f(x) g(x) = O(n^{2k})}\)