Big O, what is the complexity of summing a series of n numbers?

performance algorithm optimization complexity-theory big-o
user1032613 picture user1032613 · Feb 12, 2012 · Viewed 49k times · Source

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

svick picture svick · Feb 12, 2012

The big O notation can be used to determine the growth rate of any function.

In this case, it seems the book is not talking about the time complexity of computing the value, but about the value itself. And n(n+1)/2 is O(n^2).

Related questions

Big O, how do you calculate/approximate it?

Most people with a degree in CS will certainly know what Big O stands for. It helps us to measure how well an algorithm scales. But I'm curious, how do you calculate or approximate the complexity of your algorithms?

Read More
Generating permutations of a set (most efficiently)

I would like to generate all permutations of a set (a collection), like so: Collection: 1, 2, 3 Permutations: {1, 2, 3} {1, 3, 2} {2, 1, 3} {2, 3, 1} {3, 1, 2} {3, 2, 1} This isn't a question of "how", in general, but more about how most efficiently. Also, I wouldn't want to generate ALL permutations and return …

Read More
Why is i-- faster than i++ in loops?

I've heard this quite a few times. Are JavaScript loops really faster when counting backward? If so, why? I've seen a few test suite examples showing that reversed loops are quicker, but I can't find any explanation as to why! …

Read More