13.7 Big-Theta
Not to be confused with Big-O.
Formalizing Order of Growth
Given some function , we can apply our last two simplifications to get the order of growth of .
For example, if , the order of growth is .
From now onward, we will refer to order of growth as (pronounced "big theta").
Order of Growth Examples
The following functions have these corresponding order of growths:
Function
Order of Growth
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 with order of growth , we write that:
and there exists some positive constants , such that...
for all values greater than some (a very large ).
Last updated