1
$\begingroup$

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 !

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – coffeemath Feb 8 '13 at 13:46
  • 1
    $\begingroup$ For the 2nd and 3rd, L'hopital it. For the first, as coffeemath said use the formulae. Integral approximation is also fine. $\endgroup$ – Ishan Banerjee Feb 8 '13 at 14:59
1
$\begingroup$

$$ 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?

$\endgroup$
  • $\begingroup$ This is very good explanation. Thank you very much $\endgroup$ – SyndicatorBBB Feb 8 '13 at 18:49
  • $\begingroup$ You are welcome $\endgroup$ – Alex Feb 8 '13 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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