> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/13.-asymptotics-i/13.7-big-theta.md).

# 13.7 Big-Theta

{% embed url="<https://www.youtube.com/watch?ab_channel=JoshHug&v=CGdubALgQw4>" %}

### Formalizing Order of Growth

Given some function $$Q(N)$$, we can apply our last two simplifications to get the order of growth of $$Q(N)$$.&#x20;

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").&#x20;

### Order of Growth Examples

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* $$\Theta (\text{\_\_})$$. In other words, it belongs to the family of functions that have that same order of growth.

### Formal Definition

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