0
$\begingroup$

I'm curious if my asymptotic analysis of these functions are correct. I know the process is to strip the constants and then get to where its just comparing functions and taking limit to infinite and checking the result to see which is bigger is the process. I did do that already but I have some doubts on my results of which is bigger. Are these results correct?

  1. $6\log_6(n^6 + 2n^3) + 4n^\frac {9}{10}$

  2. $4n^\frac {1}{2} + 3n^\frac{8}{10} + 2$

  3. $8 \log_3(2n^2+n+2) + 9 \log_8(4n^3+6n^2+25)$

  4. $6(n+23) \log_2(3n^2+19n+2)+6n+24$

  5. $4\times6^{n+5} + 8\times3^{n+9}$

  6. $4^{12}$

  7. $2n^{3} + 4^{3n} + 9\times 12^{n}$

  8. $7\times2^{\log_3(n^{2}+4n)}$

  9. $\sum_{i=1}^{300} 4^i$

  10. $\sqrt{4n^2+3n+81}$

Answers I got for these functions

  1. $\Theta(n^c)$
  2. $\Theta(n^c)$
  3. $\Theta(\log_2(n))$
  4. $\Theta(n \log_2(n))$
  5. $\Theta(c^n)$
  6. $\Theta(1)$
  7. $\Theta(12^n)$
  8. $\Theta(1)$
  9. $\Theta(n^2)$

10.$\Theta(\sqrt(n))$

$\endgroup$
1
  • $\begingroup$ 7, 8, 9 and 10 are wrong. For 7, $4^3> 12$. For 8, $2^{\log_3(n^2)} = n^c$. For 9, this is a constant (no $n$ involved). For 10, $\sqrt{n^2} = n$. $\endgroup$
    – Clement C.
    Commented Mar 24, 2015 at 17:42

1 Answer 1

0
$\begingroup$

As stated in a comment:

  1. Correct ($c=\frac{9}{10}$).
  2. Correct ($c=\frac{8}{10}=\frac45$).
  3. Correct.
  4. Correct (to be even more precise, this is asymptotically equivalent to $6n\log_2(n^2)=12n\log_2 n$)
  5. Correct (for $c = 6$ (this is equivalent to $4\cdot 6^5\cdot 6^n$, as $3^n = o(6^n)$)
  6. Correct (no matter how big, this is a constant).
  7. Incorrect: $4^{3n} \gg 12^n$ (as $4^3=64$)
  8. Incorrect: $2^{\log_3(n^2)} = 2^{\frac{2}{\log_2 3}\log_2 n} = n^{\frac{2}{\log_2 3}}\to\infty$.
  9. Incorrect: this is $\Theta(1)$ (even expressed like this, this is a constant: there is no $n$ in the picture).
  10. Incorrect: this is asymptotically equivalent to $\sqrt{4n^2}=2n$, and therefore is $\Theta(n)$.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .