User:Itai/Big-O

Notation	Intuition	Definition
$f(n)\in O(g(n))$	$f$ is asymptotically upper bounded by $g$ (up to constant factor)	$\exists (C>0),n_{0}:\forall (n>n_{0})\;|f(n)|\leq |Cg(n)|$
$f(n)\in \Omega (g(n))$	$f$ is asymptotically lower bounded by $g$ (up to constant factor)	$\exists (C>0),n_{0}:\forall (n>n_{0})\;|Cg(n)|\leq |f(n)|$
$f(n)\in \Theta (g(n))$	$f$ is bounded tightly by $g$ asymptotically	$\exists (C,C'>0),n_{0}:\forall (n>n_{0})\;|Cg(n)|<|f(n)|<|C'g(n)|$
$f(n)\in o(g(n))$	$f$ is dominated by $g$ asymptotically	$\forall (C>0),\exists n_{0}:\forall (n>n_{0})\;|f(n)|<|Cg(n)|$
$f(n)\in \omega (g(n))$	$f$ dominates $g$ asymptotically	$\forall (C>0),\exists n_{0}:\forall (n>n_{0})\;|Cg(n)|<|f(n)|$
$f(n)\sim g(n)$	asymptotically equal	$\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=1$