Given some monotonically growing function, is there any way to show that $\Theta(\sum_\limits{i = 1}^{n}f(i)) = \Theta(nf(n))$? I know for a fact that this holds for the identity function $f(n) = n$. Indeed: $\sum_\limits{i = 1}^n i = n(n + 1)/2$. What about any other monotonically growing functions of $f$?
Asked
Active
Viewed 336 times
2
-
1Hint: $$f(1) + f(2) + \cdots + f(n) \le f(n) + f(n) + \cdots + f(n) = nf(n)$$ – MathMajor Dec 27 '16 at 01:09
-
2@skizeey Do you mean $\Theta(\sum_{i = 1}^n f(i)) = \Theta(n f(\color{red}{n}))$? – Olivier Oloa Dec 27 '16 at 01:14
-
1@OlivierOloa yes! Thanks. – Sal Rahman Dec 27 '16 at 01:26
1 Answers
3
It is not true in general. Take for example $f(n)=2^n$ Then $\sum_{i=1}^n f(i)=2^{n+1}-2=\Theta(2^n)$, and obviously $\sum_{i=1}^n f(i)\ne\Theta(n\cdot 2^n)$
Momo
- 16,027