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

Question

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

$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 05:28
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 05: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 05:51
Yes that is why it confused me. I wanted to make sure it is big oh. — gopal, Jun 28 '13 at 06:12

score 2 · Accepted Answer · answered Jun 28 '13 at 06:28

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

1 Answers1