Big Oh Notation

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)\in 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 best-known upper bound, actually care about in practice)
  • Lower bounded = $\Omega$ (notoriously difficult to prove)
  • Theta bounded = $\Theta$

• 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)=\Omega (g(n))$ means $c.g(n)$ is lower bound on $f(n)$
  • $f(n)=\Theta (g(n))$ means
    • $c_1.g(n)$ is upper bound on $f(n)$
    • and $c_2.g(n)$ is lower bound on $f(n)$
  • $\in \Omega ,O,\Theta$ 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$