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