Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have left with some functions I can't find witenesses for proving/disproving Big Ω equalities relations.

Here are the three relations:

  1. $ \sum\limits_{i=1}^{n} (i^3 - i ^2) = \Omega(n^4) $
  2. $log(n-\sqrt{n}) = \Omega(logn)$
  3. $log(n+\sqrt{n}) = \Omega(logn)$

For the first one I tried to split the sum but to no avail. The second and the third - I don't even have an idea how to start proving/disproving this equality..

Thank you very much !

share|improve this question
1  
For the first one there are known formulas for $\sum i^3$ and for $\sum i^2$ where $i=1..n$. Namely $[n(n+1)/2]^3$ and $n(n+1)(2n+1)/6$ respectively. This may help; I don't know what $\Omega(n^4)$ means, just not up on the notation. –  coffeemath Feb 8 '13 at 13:46
1  
For the 2nd and 3rd, L'hopital it. For the first, as coffeemath said use the formulae. Integral approximation is also fine. –  Ishan Banerjee Feb 8 '13 at 14:59
add comment

1 Answer 1

up vote 1 down vote accepted

$$ S_1 = \sum_{k=1}^{n}(k^3-k^2)\geq \frac{n^4}{4}-\frac{n^3}{3} = \Omega (n^4) $$

The $\geq$ is due to comparison with the integral. $$ S_2=\log (n-\sqrt{n})=\log (\sqrt{n}(\sqrt{n}-1))\geq \frac{1}{2}\log n + \frac{1}{2} \log n - \log 2 \geq \log n -\log 2 = \Omega(\log n) $$ The first $\geq$ is due to $\log (\sqrt{n}-1) \geq \log \big( \frac{\sqrt{n}}{2} \big) $

can you handle the third one from here?

share|improve this answer
    
This is very good explanation. Thank you very much –  SyndicatorBBB Feb 8 '13 at 18:49
    
You are welcome –  Alex Feb 8 '13 at 18:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.