tags : Complexity Theory, Math
What is it?
 A language to talk about functions
 We’re just talking about properties of functions
 We’re not talking about meanings
 Programmers use this notation to describe complexity, but there’s absolutely nothing stopping us from using asymptotic notation with other types of equations, things like the population of rabbits over time, the temperature given a change in pressure, and so forth.
The notation
 $f(n)=O(g(n))$
 actually means $f(n)∈O(g(n))$
 read as ”$f(n)$ is order $g(n)$” or ”$f(n)$ is $O(g(n))$”
The Details

Functions are sometimes complex (Wiggly curve in diagram), so it’s easier to talk about the function in terms of upper bound and lower bound.

What are the bounds?
 Upper bounded = $O$ (best known upper bound, or a simplification of the bestknown upper bound, actually care about in practice)
 Lower bounded = $Ω$ (notoriously difficult to prove)
 Theta bounded = $Θ$

With Big Oh Notation, we are able to reason about complex functions because we can see the upper and lower bound of the function.
 $f(n)=O(g(n))$ means $c.g(n)$ is upper bound on $f(n)$
 $f(n)=Ω(g(n))$ means $c.g(n)$ is lower bound on $f(n)$
 $f(n)=Θ(g(n))$ means
 $c_{1}.g(n)$ is upper bound on $f(n)$
 and $c_{2}.g(n)$ is lower bound on $f(n)$
 $∈Ω,O,Θ$ relationships for a function will be satisfied for $c$ and $n_{0}$.
 $c$ is
constant
independent of $n$  $n_{0}$ is a
constant
, a threshold beyond which these are satisfied  We do not care about small values of $n$
 $c$ is