Difficulty proving / finding witnesses for the following Functions (Big O and Big Ω and $\Theta)

Question

I have left with some functions I can't find witenesses for proving Big O and Big Ω and Big $\Theta$ relations.

Notice that I should prove the following using the defintion and not any complex method (i.e. limits, integrals and so....)

Here are the function I need your help / hint how to start after using the defintion $ (n_0, c, \dots )$:

1. $n^5 -2\log n = \Omega(n^5)$

2. $\log(n^2 +13) = \Theta(\log n)$

3. If $f(n) = O (g(n)) $ then $2^{f(n)} = O(2^{g(n)})$

Notice that the 3rd one contains some "Text Math" because I couldn't put an expression in the exponent.

That's all,

Thank you in advance!

Answer 1

HINTS:

(1) Note that $\log n<n$, so $n^5-2\log n>n^5-2n$; now show that $2n\le\frac12n^5$ for $n\ge 2$.

(2) Clearly $\log n\le\log(n^2+13)$. In the other direction, $\log(n^2+13)\le\log n^3=3\log n$ for $n\ge 3$, as you can verify by proving that $n^3\ge n^2+13$ for $n\ge 3$.

(3) is false: try $f(n)=2n$ and $g(n)=n$.