4. The Big-Oh family

13/02/23

Big-Omega

Given functions $f(n)$ and $g(n)$ we say that $f(n) == \Omega(g(n))$ if there are (strictly) positive constants $c$ and $n_0$ such that $f(n) \ge cg(n)$ for all $n\ge n_0$

Grows at least as fast as g(n) at large n

It is reflexive, NOT symmetric but is transitive

Linking big-Oh and big-Omega

Omega expresses 'grows as least as fast as' Oh expresses 'grows at most as fast as'

Big-Theta

Given functions $f(n)$ and $g(n)$ we say that $f(n) == \Theta(g(n))$ if there are positive constants $c',c'',n_0$ such that $f(n) \le c' g(n)$ $f(n) \gt c'' g(n)$ for all $n\ge n_0$

Big Theta is an equivalence relation. Behaves like a equality