0
$\begingroup$

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!

  • 0
    Thank you @Berci, working on it.2012-11-01

1 Answers 1

2

HINTS:

(1) Note that $\log 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$.

  • 0
    @Guy: You’re wel$c$ome!2012-11-01