# Asymptotic notation
## Big-$$\Theta$$(Big-Theta) notation
Logarithms grow more slowly than polynomials. That is, $$\Theta(\log\_2 n)$$ grows more slowly than $$\Theta(n^a)$$ for *any* positive constant $$a$$. But since the value of $$\log\_2 n$$, increases as $$n$$ increases, $$\Theta(\log\_2 n)$$ grows faster than $$\Theta(1)$$.
The following graph compares the growth of $$1$$, $$n$$, and $$\log\_2 n$$:
Here's a list of functions in asymptotic notation that we often encounter when analyzing algorithms, ordered by slowest to fastest growing:
1. $$\Theta(1)$$
2. $$\Theta(\log\_2 n)$$
3. $$\Theta(n)$$
4. $$\Theta(n \log\_2 n)$$
5. $$\Theta(n^2)$$
6. $$\Theta(n^2 \log\_2 n)$$
7. $$\Theta(n^3)$$
8. $$\Theta(2^n)$$
9. $$\Theta(n!)$$
Note that an exponential function a^nana, start superscript, $$n > 1$$, grows faster than any polynomial function $$n^b$$, where $$b$$ is any constant.
A function has **"constant" growth** if its output does not change based on the input, the $$n$$. The easy way to identify constant functions is find those that have no $$n$$ in their expression anywhere, or have $$n^0$$, In this case, $$1$$ and $$1000$$ are constant.
A function has **"linear" growth** if its output increases linearly with the size of its input. The way to identify linear functions is find those where $$n$$ is never raised to a power (although $$n^1$$is OK) or used as a power. In this case, $$\bf3n$$ and $$\bf(3/2)n$$ are linear.
A function has **"polynomial" growth** if its output increases according to a polynomial expression. The way to identify polynomial functions is to find those where $$n$$ is raised to some constant power. In this case, $$\bf2n^3$$ and $$\bf3n^2$$ are polynomial.
A function has **"exponential" growth** if its output increases according to an exponential expression. The way to identify exponential functions is to find those where a constant is raised to some expression involving $$n$$. In this case, $$\bf2^n$$ and $$\bf(3/2)^n$$ are exponential.
We have several different types of functions here, so we start by thinking about the general properties of those function types and how their rate of growth compares. Here's a reminder of different function types shown here, in order of their growth:
1. Constant functions
2. Logarithmic functions
3. Linear functions
4. Linearithmic functions
5. Polynomial functions
6. Exponential functions
### Which type is each of the presented options?
1. Constant functions:
* $$64$$
2. Logarithmic functions
* $$\log\_8{n}$$, $$\log\_2{n}$$
3. Linear functions
* $$4n$$
4. Linearithmic functions
* $$n,\log\_2{n}$$, $$n,\log\_8{n}$$
5. Polynomial functions
* $$8n^2$$, $$6n^3$$
6. Exponential functions
* $$8^{2n}$$
Within the logarithmic functions, the lesser bases grow more quickly than the higher bases - so $$\log\_2{n}$$ will grow more quickly than $$\log\_8{n}$$. You can see that in the graph below:
The linearithmic functions are those that multiply linear terms by a logarithm, of the form $$n,\log\_k n$$. With the nnn being the same in both, then the growth is dependent on the base of the logarithms. And as we just stated, the lesser bases grow more quickly than the higher bases - so $$n,\log\_2{n}$$ will grow more quickly than $$n,\log\_6{n}$$. You can see that in the graph below:
Within the polynomial functions, $$8n^2$$ will grow more slowly than $$6n^3$$ since it has a lesser exponent. We don't even have to look at the constants in front, since the exponent is more significant.
To conclude, the correct order of the functions would be:
* $$64$$
* $$\log\_8{n}$$
* $$\log\_2{n}$$
* $$4n$$
* $$n,\log\_6{n}$$
* $$n,\log\_2{n}$$
* $$8n^2$$, $$6n^3$$
* $$8^{2n}$$
## Big-O notation
\
If a running time is $$O(f(n))$$, then for large enough $$n$$, the running time is at most $$k \cdot f(n)$$ for some constant $$k$$. Here's how to think of a running time that is $$O(f(n))$$:
We use big-O notation for **asymptotic upper bounds**, since it bounds the growth of the running time from above for large enough input sizes.
## Big-Ω (Big-Omega) notation
Sometimes, we want to say that an algorithm takes *at least* a certain amount of time, without providing an upper bound. We use big-Ω notation; that's the Greek letter "omega."
If a running time is $$\Omega(f(n))$$, then for large enough $$n$$, the running time is at least $$k \cdot f(n)$$ for some constant $$k$$. Here's how to think of a running time that is $$\Omega(f(n))$$:
We say that the running time is "big-Ω of $$f(n)$$. We use big-Ω notation for **asymptotic lower bounds**, since it bounds the growth of the running time from below for large enough input sizes.
Just as $$\Theta(f(n))$$ automatically implies $$O(f(n))$$, it also automatically implies $$\Omega(f(n))$$. So we can say that the worst-case running time of binary search is $$\Omega(\log\_2 n)$$.
###
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://stephanosterburg.gitbook.io/scrapbook/math/algorithm-khan-academy/asymptotic-notation.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.