# Some big-theta and big-omega notation question

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

• 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.
– zwim
Dec 7, 2020 at 19:05
• 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. Dec 7, 2020 at 19:20
• $\sqrt$ is an increasing function so $n^4>n\implies\sqrt{n^4}>\sqrt{n}$.
– zwim
Dec 7, 2020 at 19:22
• therefore c1 should be 1 and c2 should be 2? Dec 7, 2020 at 20:28

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.