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$?
2026-04-18 18:33:05.1776537185
Any way to show that $\Theta(\sum_{i = 1}^n f(i)) = \Theta(n f(n))$?
339 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
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)$