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

690 Views Asked by At

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

1

There are 1 best solutions below

0
On BEST ANSWER

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