Big-Oh Notation

Alternative formulation of parts of calculus.

def. Big-Oh Notation. for functions $f,g$, we say $f(n)=O(g(n))$ iff:

• Definition 1:

$$\exists c\in {\mathbb{R}}^{+}\forall n\in {\mathbb{N}}^{+},f(n)\le c\cdot g(n)$$

• Definition 2:

$$\underset{n\to \infty }{\lim }\text{sup}(f(n))<\infty$$

• ⇒ Intuitive Understanding: $f=O(g)\approx f<g$

def. Big-Omega Notation. For functions $f,g$ we say $f=\Omega (g)$ iff $g=O(f)$

def. Big-Theta Notation

$$f=O(g)\text{ and }f=\Omega (g)⟹f=\Theta (g)$$