asked over stackoverflow

Question

I always thought the complexity of:

1 + 2 + 3 + ... + n is O(n), and summing two n by n matrices would be O(n^2).

But today I read from a textbook, "by the formula for the sum of the first n integers, this is n(n+1)/2" and then thus: (1/2)n^2 + (1/2)n, and thus O(n^2).

What am I missing here?

Answer 1

actually if someone ask TC of value produced by sum of n natural numbers then TC=O(n²)

if asked TC of the computation to produce this sum then TC=O(n)

---

it's just like TC of multiplication for factorial n (n!) is O(n)

while TC of value produced is O(nⁿ)