# How to evaluate Θ, or O and Ω from function

I have to evaluate the $\Theta$, $O$, $\Omega$. I all the time I thing that:

$$\sum_{k=1}^nk = \Theta(n)$$

Because I have $n$ steps. But in some papers I have found that:

$$\sum_{k=1}^nk = \frac{n(n+1)}{2} = \Theta(n^2)$$

So I am really confuse can you please clear up?

Also why is $\ln{n!}$ equal to $\Theta(n \log{n})$..

-
Do you mean $$\sum_{k=1}^Nk$$ in the displayed formulas? – Brian M. Scott May 13 '12 at 18:37
Well, think of an n-iteration loop with amount of work $1,2,3,…,n.$ Note that the amount of work in every iteration is at most $n$ (i.e. $O(n)$). The total amount of work is clearly $n×O(n),$ or $O(n^2).$ For $\ln n!,$ think of log of products. We have $\ln n!= \ln n+ \ln (n−1) + … + \ln 2+ \ln 1.$ Again that's $n×O(\ln n)$ because the sum has $n$ terms, and each term is upper bounded by $\ln n.$ Converting $\ln$ to $\log$ is a matter of constants. – user2468 May 13 '12 at 19:04
J.D.'s comment proves the upper bounds ($O(\cdots)$) but ignores the matching lower bounds ($\Omega(\cdots)$). Half the terms in the sum are at least $n/2$, so the sum is at least $n^2/4 = \Omega(n^2)$. Since we already know the sum is $O(n^2)$, we conclude that it is also $\Theta(n^2)$. Similarly, half the terms in the sum $\ln n + \ln (n-1) + \cdots + \ln 1$ are at least $\ln (n/2) = \ln n - \ln 2$, so $\ln n! \ge (n/2)\ln (n/2) = (n\ln n)/2 - n (\ln 2)/2 = \Omega(n\log n)$. Since we already know that $\ln n! = O(n\log n)$, we conclude that $\ln n! = \Theta(n\log n)$. – JeffE May 13 '12 at 19:12
but when we write program for sum we get: for(i to n) sum += i.. Why $n^2$? – radeklos May 13 '12 at 19:22
@JeffE Ops. Sorry I misread the question! – user2468 May 13 '12 at 22:57

If you have one loop:

    for i = 1 to n
sun += i


then running time will be: $$\sum_{i=1}^n1 = n = \Theta(n)$$

But if you have nested loops:

    for i = 1 to n
for j = 0 to i
sun += j


then running time will be: $$\sum_{i=1}^ni = \frac{n(n+1)}{2} = \Theta(n^2)$$

-