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
    Do you mean $$\sum_{k=1}^Nk$$ in the displayed formulas?2012-05-13
  • 0
    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.2012-05-13
  • 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)$.2012-05-13
  • 0
    but when we write program for sum we get: for(i to n) sum += i.. Why $ n^2 $?2012-05-13
  • 0
    @JeffE Ops. Sorry I misread the question!2012-05-13
  • 0
    @Radecek I think you have a misunderstanding here. A loop of $n$ iterations can have a time complexity more than $n.$ It essentially have time complexity $n\times s,$ where $s$ is the complexity of a single iteration. (well, more accurately: $\sum_{i=1}^{n} s_i.$)2012-05-13
  • 0
    @Radecek: Regarding your comment, the equation $\sum_{k=1}^n k = \Theta(n)$ is not talking about the time it takes to calculate the sum $1 + 2 + \cdots + n$. It is saying that if your program takes $1 + 2 + \cdots + n$ steps to compute whatever other thing it's computing, then the number of steps it takes is $\Theta(n)$.2012-08-02
  • 0
    "evaluate" is a weird word in this context.2012-08-02

1 Answers 1