# Seatwork (Asymptotic Analysis)

Which complexity classes do these functions belong to? Write the complexity class in terms of $\Theta$. Show also the Asymptotic Analysis of the two functions f(n) and g(n) based on the variables specified in the functions using the **Limit Definition**. Number 1 is done as an example.

---

${For \space Example}$
**1.** $3n^2+40n-5$
$3n^2+40n-5$ $\epsilon$ $\Theta$$(3n^2)$ *using the Sum of Functions Reduction Rule*
$3n^2+40n-5$ $\epsilon$ $\Theta$$(n^2)$ *using the Dropping the Coefficient Reduction Rule*

**Asymptotic Analysis using the Limit Definition**

$f(n) = 40n$
$g(n) = 3n^2$

$\lim_{n \to \infty} \frac{40n}{3n^2}$
$\space\space\space\space\space\space\space\space\space\space\space\space\space$$\frac{\frac{d}{dn} (40n)}{\frac{d}{dn} (3n^2)}$ *using L'Hopital's Rule*
$\space\space\space\space\space\space\space\space\space\space\space\space\space$$\lim_{n \to \infty} \frac{40}{6n} \approx 0$ *based on the limit definition...*
$\therefore 40n\space\epsilon\space O(3n^2)$ which means $3n^2$ is more complex

---

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}}$