How to apply Big-omega to a summation.

Question

Someone can help me with this problem, I do not know how to proceed correctly.

Out of curiosity, what would be the Big-Omega cost of the recursion of Hanoi?

Answer 1

$$\sum_{i=1}^n i=\frac{n(n+1)}2.$$ By the definition of $f(n)\in O(n)$ it should be true that

$$\lim_{n\to\infty}\frac{\sum_{i=1}^n i}n= \text{some constant}.$$

But $$\lim_{n\to\infty}\frac{\frac{n(n+1)}2}n=\lim_{n\to\infty}\frac12(n+1)=\infty$$

and not a constant.

That is,

$$\sum_{i=1}^n i\not\in O(n).$$

EDIT

I am sorry for mistaking "big $\Omega$" for "big O". Freud could exlplain ... There are different definitions of the "big $\Omega$" notation. Here is the Knuth version:

$$f(n)\in \Omega(g(n)) \text{ if and only if } g(n)\in O(f(n)).$$

In our case

$$\frac{n(n+1)}{2}\in \Omega (n)$$

If and only if

$$n \in O\left(\frac{n(n+1)}{2}\right).$$

Now, you know what to do. The answer is Yes.