Big-Theta Notation

Big-Theta provides an asymptotic bound for a given growth function using a combination of Big-O Notation and Big-Omega Notation.

Formal Definition §

Big-Theta Notation

$$f(n)\in \Theta (g(n))⟺f(n)\in O(g(x))\text{ and }f(n)\in \Omega (g(n))$$

$$⟺\exists n_0,c_1>0,c_2>0,\forall n>n_0,c_{1}g(n)\le f(n)\le c_{2}g(n)$$

Note

• $f(n),g(n)$ = Growth Function $f(n)$
• $O(g(n))$ = Big-O Notation for $g(n)$
• $\Omega (g(n))$ = Big-Omega Notation for $g(n)$
• $n_0$ = Initial n value for which $f(n)$ is bounded by both $c_1\cdot g(n)$ and $c_2\cdot g(n)$
• $c$ = Scaling constant for $g(n)$
• $c_2>c_1$

Keep in note that there must be the same value of $n_0$ for both ceiling and growth functions.

Common Big-O Functions §

(and where they are found)

Time Complexity	Found In
$1$	Running time independent of input.
$\log (n)$	Typical for “divide and conquer” solutions, for example, lookup in a balanced search tree.
$n$	Linear. When each input element must be processed once.
$n\log (n)$	Each input element processed once and processing involves other elements too, for example, sorting.
$n^2,n^3$	Quadratic, cubic. Processing all pairs (triples) of elements.
$2^n$	Exponential. Processing all subsets of elements.