0
$\begingroup$

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

  • 0
    "evaluate" is a weird word in this context.2012-08-02

1 Answers 1

2

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