I am struggling to understand why this property of asymptotic notation is true

enter image description here


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.