# Seatwork: Rules of Asymptotic Notation

### Questions

Which complexity class do these functions belong to? Write the complexity class in terms of $\Theta$.

1. $3n^2+40n-5$

2. $8n+6n+log_3n$

3. $log_5 n + 6 log_3 n$

4. $log_5n+\sqrt{n}$

5. $8log_3{(log_3 n)} + log_5n$

6. $2n + 2^n + 50 n^3$

7. $2^7 + n^2 + 50n^3$

8. $nlog_2 n + 5n$

9. $6n + 3n^2 + 4$

10. $4 + 5\sqrt{n} + \sqrt[3]{n^2}$

11. $2(log_5 n)^2 + 8n^{\frac{2}{3}}$

### Answers

1. Quadratic or $\Theta(n^2)$
2. Linear or $\Theta(n)$
3. Polylog or $\Theta(logn)$
4. Fractional Power or $\Theta(n^{\frac{1}{2}})$
5. Polylog or $\Theta(logn)$
6. Exponential or $\Theta(2^{n})$
7. Polynomial or $\Theta(n^{3})$
8. Loglinear or $\Theta(nlogn)$
9. Quadratic or $\Theta(n^{2})$
10. Fractional Power or $\Theta(n^{\frac{2}{3}})$
11. Fractional Power or $\Theta(n^{\frac{2}{3}})$

**Limit Solution for number 11**
$$
\begin{align*}
&= \lim_{n \to \infty }\frac{2(\log_{5}n)^{2}}{8n^{\frac{2}{3}}}\\
&= \lim_{n \to \infty }\frac{4\log_{5}n\left(\frac{1}{nln5}\right) }{\frac{2}{3}8n^{-\frac{1}{3}}}\\
&= \lim_{n \to \infty }\frac{4\log_{5}n}{\frac{16}{3}n^{\frac{2}{3}}ln5}\\
&= \lim_{n \to \infty }\frac{\frac{1}{nln5}}{\frac{2}{3}\cdot \frac{4}{3}n^{-\frac{1}{3}}ln5}\\
&=\lim_{n \to \infty } \frac{n^{\frac{1}{3}}}{\frac{8}{9}n(ln5)^{2}}\\
&=\lim_{n \to \infty } \frac{1}{{\frac{8}{9}n^{\frac{2}{3}}(ln5)^{2}}}\\
&= 0
\end{align*}
$$

Therefore the denominator is more complex and is more dominant.