Comment on page
13.7 Big-Theta
Not to be confused with Big-O.
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").
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.
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 modified 9mo ago