Comment on page

# 13.7 Big-Theta

Not to be confused with Big-O.

### 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
. 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$
).