Comment on page

# 13.7 Big-Theta

Not to be confused with Big-O.

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"). 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.

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$

).Last modified 9mo ago