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)Q(N)
, we can apply our last two simplifications to get the order of growth of Q(N)Q(N)Q(N)
. 
For example, if Q(N)=3N3+N2Q(N)=3N^3+N^2Q(N)=3N3+N2
, the order of growth is N3N^3N3
.
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^4N3+3N4
​
​N4N^4N4
​
​1/N+N31/N + N^31/N+N3
​
​N3N^3N3
​
​1/N+51/N + 51/N+5
​
​111
​
​NeN+NNe^N+NNeN+N
​
​NeNNe^NNeN
​
​40sin(N)+4N240sin(N)+4N^240sin(N)+4N2
​
​N2N^2N2
​
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)R(N)
 with order of growth f(N)f(N)f(N)
, we write that:
​R(N)∈Θ(f(N))R(N) \in \Theta(f(N))R(N)∈Θ(f(N))
 and there exists some positive constants k1k_1k1​
, k2k_2k2​
 such that...
​k1⋅f(N)≤R(N)≤k2⋅f(N)k_1 \cdot f(N) \leq R(N) \leq k_2\cdot f(N)k1​⋅f(N)≤R(N)≤k2​⋅f(N)
 for all values NNN
 greater than some N0N_0N0​
 (a very large NNN
).

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$

13.6 Simplified Analysis Process

13.8 Big-O

Last modified 9mo ago