Comment on page

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:
Function
Order of Growth
N3+3N4N^3+3N^4
N4N^4
1/N+N31/N + N^3
N3N^3
1/N+51/N + 5
11
NeN+NNe^N+N
NeNNe^N
40sin(N)+4N240sin(N)+4N^2
N2N^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)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
).