O-Notation

\(\Theta\)-Notation

$$ \Theta(g(n)) = \{ f(n) \mid \exists c_1, c_2, n_0 : 0 \leq c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n), \forall n \geq n_0 \} $$

  • Intuitively, “\(f(n) \in \Theta(g(n))\)” means that \(f(n)\) and \(g(n)\) are asymptotically equivalent
    • They have the same growth rates for large \(n\)
    • E.g. \(4n^2, (8n^2+2n-3), (n^2/5+\sqrt{n}-10\log{n}), n(n-3)\) are all asymptotically equivalent because if \(n\) becomes large the dominant (fastest growing) term is \(n^2\)
    • With \(c_1, c_2\) we say that “the constants do not matter because you may pick \(c_1\) and \(c_2\) however you like to satisfy these conditions”
    • With \(n_0\) we say that “we are only interested in large \(n\), since you only have to satisfy the condition for all \(n\) bigger than \(n_0\), and you may make \(n_0\) as big as you want”

\(\mathcal{O}\)-Notation and \(\Omega\)-Notation

  • The definition of \(\Theta\)-notation relies on proving both a lower and upper asymptotic bound
    • Sometimes we might only be interested in proving one or the other
  • \(\mathcal{O}\)-notation allows us to state asymptotic upper bounds
  • \(\Theta\)-notation allows us to state asymptotic lower bounds
  • Observe that \(f(n) \in \Theta(g(n))\) if and only if \(f(n) \in \mathcal{O}(g(n))\) and \(f(n) \in \Omega(g(n))\)

\(\mathcal{O}\)-Notation

$$ \mathcal{O}(g(n)) = \{ f(n) \mid \exists c, n_0 : 0 \leq f(n) \leq c \cdot g(n), \forall n \geq n_0 \} $$

  • Intuitively, “\(f(n) \in \mathcal{O}(g(n))\)” means that \(f(n)\) grows asymptotically a the same rate or slower than \(g(n)\)

\(\Theta\)-Notation

$$ \Omega(g(n)) = \{ f(n) \mid \exists c, n_0 : 0 \leq c \cdot g(n) \leq f(n), \forall n \geq n_0 \} $$

  • Intuitively, “\(f(n) \in \Omega(g(n))\)” means that \(f(n)\) grows asymptotically at the same rate or faster than \(g(n)\)

Asymptotic Intuition

  • \(\Theta(1)\): Constant time; you can’t beat that!
  • \(\Theta(\log n)\): Most efficient data structures operate in this speed for a single access. Also it is the time it takes to find an object in a sorted list of length n by binary search Most efficient data structures operate in this speed for a single access. Also it is the time it takes to find an object in a sorted list of length n by binary search.
  • \(\Theta(n)\): Fastest time that an algorithm can run, given that you need \(\Theta(n)\) time just to read in all the data.
  • \(\Theta(n \log n)\): Running time of the fastest sorting algorithms. Since many problems require sorting the input, this is still considered fast.
  • \(\Theta(n^2), \Theta(n^3), \dots\): Polynomial time. These running times are acceptable if the exponent is small or when the data size is not too large (e.g. \(n \leq 1000\)).
  • \(\Theta(2^n), \Theta(3^n), \dots\): Exponential time. This is only acceptable if you know that the input are small (e.g. \(n \leq 50\)) or you know that this is a worst-case running time that rarely occurs in practice.
  • \(\Theta(n!), \Theta(n^n)\): Only acceptable for really small inputs (e.g. \(n \leq 20\)).

References