13.7 Big-Theta

Not to be confused with Big-O.

Formalizing Order of Growth

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

For example, if Q(N)=3N3+N2Q(N)=3N^3+N^2, the order of growth is N3N^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:

FunctionOrder of Growth

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)R(N) with order of growth f(N)f(N), we write that:

R(N)Θ(f(N))R(N) \in \Theta(f(N)) and there exists some positive constants k1k_1, k2k_2 such that...

k1f(N)R(N)k2f(N)k_1 \cdot f(N) \leq R(N) \leq k_2\cdot f(N) for all values NN greater than some N0N_0 (a very large NN).

Last updated