0

I got this question wrong on my midterm, I need someone to explain how did they get the answer.

$$ A(n) = \frac{2+3n}{5\sqrt{n}(1+4\log{n})} $$ $$ B(n) = \frac{2\sqrt{n}(4+7\log{n})}{\sqrt{n} + 5\log{n}} $$ $$ C(n) = 7\log{n} + 8^{(\frac{\log{n}}{9} )} $$

Answer: $$B(n) = Ө(\log {n})$$

$$ C(n) = Ө(n^\frac{1}{3}) $$

$$A(n) = Ө{(\frac{\sqrt{n}}{\log{n}})}$$

so the answer is B(n) , C(n) , A(n)

How did they get the big-Ө, can anyone explain?

user38543
  • 11

1 Answers1

1

Using the fact that if $f_1=\Theta(g_1)$ and $f_2=\Theta(g_2)$, then $f_1+f_2 = \Theta(\max(g_1, g_2))$, $f_1 f_2 = \Theta(g_1 g_2)$ and $const f_1 = \Theta(g_1)$: $$2 + 3n = \Theta(n)\\ 5\sqrt n (1+4\log n) = \Theta(\sqrt n \log n) $$ and $$A(n) = \Theta(\frac{n}{\sqrt n\log n}) = \Theta(\frac{\sqrt n}{\log n})$$

Do the similar analysis for the other two expressions.

confucious
  • 340