0
$\begingroup$

Let $f : \mathbb{N} \rightarrow \mathbb{R}$ be the function $f ( n ) = n ^ { 2 } + \sqrt { n }$. Determine whether the following statement is true or false, providing a proof for your answer.

$ f(n) = \Theta(n^2) $

$ \log_2[f(n)] = \Theta(\log_2n) $

$ 2^{f(n)} = \Theta(2{n^2}) $

$2 ^ { 2 ^ { f ( n ) } } = \Omega ( g )$, where $g(1) = 1$, $g(2) = 2$, and $g(n) = [g(n - 1)] ^2 + [g(n - 2)] ^2$ for $n \ge 3$.

How can I get a prove to determine the abovementioned is true or false

for a),

what I have got for the first questionnow is:

I have $ c_1, c_2 , n_0 > 0$

c_1 $ \leq n^2 + \sqrt(n) \leq c_2 $

c_1 $ \leq 1 + \frac{1}{n^\frac{3}{2}} \leq c_2 $

So how can I continue to prove the Big theta notation? I don't understand how to choose the c

$\endgroup$
4
  • $\begingroup$ Use for instance $n>1\implies n^4>n^2>n$ now take square root to get $0<\sqrt{n}<n^2$ do you see $c_1$ and $c_2$ now ? The other questions are similar. $\endgroup$
    – zwim
    Dec 7, 2020 at 19:05
  • $\begingroup$ I understand that when n > 1 them $ n^4$ grow faster than $n^2 $ also grow faster than $ n$ but I don't understand the sqrt part. Can you explain more please. $\endgroup$
    – Antonymous
    Dec 7, 2020 at 19:20
  • $\begingroup$ $\sqrt$ is an increasing function so $n^4>n\implies\sqrt{n^4}>\sqrt{n}$. $\endgroup$
    – zwim
    Dec 7, 2020 at 19:22
  • $\begingroup$ therefore c1 should be 1 and c2 should be 2? $\endgroup$
    – Antonymous
    Dec 7, 2020 at 20:28

1 Answer 1

1
$\begingroup$

Perhaps this will set you on the right track $$c_1 n^2\le n^2+\sqrt{n}\le c_2 n^2$$ Now just find $c_1$ and $c_2$, both greater than zero, that makes the inequality true as $n$ increases past some $n_0$. Once you achieve this, then you can say $$n^2+\sqrt{n}\in\Theta\left(n^2\right)$$ The same strategy applies to the other Big Theta problems.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .