# Asymptotic analysis comparision for $2^n$ and $(3/2)^n$

1) $$f(n) = 2^n\,,\quad g(n) = (3/2) ^ n$$

Is $f(n) = \Theta(g(n))$? Can someone please explain this to me ?

2)$$f(n) = n^2+\log n\,,\quad g(n) = n^2$$

I know that $f(n) = \Theta(g(n))$ but how can I get the constant $c$ to prove the equation for $\Theta$?

• Do you know the definition of "big O" notation? – Cameron Buie Jun 28 '13 at 5:20
• $0 \leq f(n) \leq c g(n)$ is that a trick question. I thought the first one is big O but I looked at solution online which says it is $\theta$. I need a confirmation hence I posted it here. – gopal Jun 28 '13 at 5:28
• How did you prove that $f=\Theta (g)$? – Mhenni Benghorbal Jun 28 '13 at 5:35
• we can do that by limits $\lim_{n \to +\infty} f(n)/g(n)$ will be a constant which is not zero. – gopal Jun 28 '13 at 5:48
• I am reading algorithm design manual by steve skeina in book it mentions if f or g doesn't dominate then we get a constant which is not 0. $0 \leq c1 g(n) \leq f(n) \leq c2 g(n)$ – gopal Jun 28 '13 at 5:51

For the second problem, just note that, $\forall n \geq 1$
$$|f(n)| = |n^2+\log n| < n^2 + n \leq 2 n^2,$$
where the fact that $\log(n) < n$ has been used. For the other inequality, observe that
$$|f(n)| = |n^2+\log n| \geq n^2,$$
since $\ln(n)\geq 0$ $\forall n\geq 1$.