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 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}) $..

share|improve this question
    
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
1  
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

1 Answer 1

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

share|improve this answer

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.