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