1
$\begingroup$

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

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ Do you know the definition of "big O" notation? $\endgroup$ – Cameron Buie Jun 28 '13 at 5:20
  • $\begingroup$ $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. $\endgroup$ – gopal Jun 28 '13 at 5:28
  • $\begingroup$ How did you prove that $ f=\Theta (g) $? $\endgroup$ – Mhenni Benghorbal Jun 28 '13 at 5:35
  • $\begingroup$ we can do that by limits $\lim_{n \to +\infty} f(n)/g(n)$ will be a constant which is not zero. $\endgroup$ – gopal Jun 28 '13 at 5:48
  • $\begingroup$ 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)$ $\endgroup$ – gopal Jun 28 '13 at 5:51
1
$\begingroup$

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

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.