I am struggling to understand why this property of asymptotic notation is true
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
In general, it is not: see Summation of asymptotic notation, Why is $\sum_{i=1}^n O(i)$ not the same as $O(1)+O(2)+\dots+O(n)$?.
But if each $O(f(k))$ term uses the same hidden constant, then it follows by expanding the sum: see https://en.wikipedia.org/wiki/Big_O_notation#Sum, Summing big-O-notation, and then apply them repeatedly.
