Notacja asymptotyczna

• Duże $O$
  • Example $O$ #1
  • Example $O$ #2
• Duże $\Omega$
  • Example $\Omega$
• Duże $\Theta$
• Małe $o$
  • Example $o$
• Mała $\omega$

Duże $O$

$f,g: \natnums \to \reals$

$$f(n) = O\big( g(n) \big) \equiv \big(~ \exists{c}~\exists{n_0}~\forall{n>n_0}: \big|f(n)\big| \le c \big|g(n)\big| ~\big)$$

Example $O$ #1

Dla $$f(n) = n^3 + O(n^2) \equiv \exists{h(n)} = O(n^2)$$ takie że $$f(n) = n^3 + h(n)$$

Example $O$ #2

$$f(n) = 10^{10}n + O\big(ln(n)\big) = O(n)$$

Duże $\Theta$

$$f(n) = \Theta\big(g(n)\big) \equiv f(n) = O\big(g(n)\big) \land f(n) = \Omega\big(g(n)\big)$$ $$\equiv \exists{c_1, c_2} \forall{n\ge{n_0}}: c_1\big|g(n)\big| \le f(n) \le c_2 \big|g(n)\big|$$

Mała $\omega$

$$f(n) = \omega\big(g(n)\big) \equiv \big(~ \forall{c}~\exists{n_0}~\forall{n\ge{n_0}}: c\big|g(n)\big| \le \big|f(n)\big| ~\big)$$