# Difficulty proving / finding witnesses for the following Functions (Big O and Big Ω and $\Theta) 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! - Just use the definitions. For 2) you may also apply this trick:$2\log n=\log(n^2)\le \log(n^2+13)\le \log(n^2+2n+1)=2\log(n+1)$. – Berci Nov 1 '12 at 19:23 @Berci I'm trying but to no avail. the -2logn in the 1st function is blocking me. – SyndicatorBBB Nov 1 '12 at 19:24 Prove that$\log x\le \frac14x^5$for$x>x_0$for some$x_0$(where their graphs meet:) – Berci Nov 1 '12 at 19:27 Thank you @Berci, working on it. – SyndicatorBBB Nov 1 '12 at 19:30 ## 1 Answer 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\$.

-
Wow, thank you! – SyndicatorBBB Nov 1 '12 at 19:29
@Guy: You’re welcome! – Brian M. Scott Nov 1 '12 at 19:30