13.7 Big-Theta

Formalizing Order of Growth

Given some function $Q(N)$, we can apply our last two simplifications to get the order of growth of $Q(N)$.

For example, if $Q(N)=3N^3+N^2$, the order of growth is $N^3$.

From now onward, we will refer to order of growth as $\Theta$ (pronounced “big theta”).

Order of Growth Examples

The following functions have these corresponding order of growths:

Function	Order of Growth
$N^3+3N^4$	$N^4$
$1/N + N^3$	$N^3$
$1/N + 5$	$1$
$Ne^N+N$	$Ne^N$
$40sin(N)+4N^2$	$N^2$

Instead of saying a function has order of growth ___, we say that the function belongs to $\Theta (\text{\_\_})$. In other words, it belongs to the family of functions that have that same order of growth.

Formal Definition

For some function $R(N)$ with order of growth $f(N)$, we write that:

$R(N) \in \Theta(f(N))$ and there exists some positive constants $k\_1$, $k\_2$ such that…

$k\_1 \cdot f(N) \leq R(N) \leq k\_2\cdot f(N)$ for all values $N$ greater than some $N\_0$ (a very large $N$).