Sum of order O (1) + O (2) + .... + O (n)

Question

What estimates the sum of O(1)+O(2)+ .... +O(n) on?

I saw his solution somewhere where it was written:

 O(n(n+1) / 2) = O(n^2) 

but I am not satisfied with this because O(1) = O(2) = constant , so for me it should only evaluate O(n) . I also saw this in Cormen:

 Σ(i=1 to n) O(i) 

There is only one anonymous function in the above expression. This function does not coincide with O(1) + O(2) + ... + O(n) , which does not actually have a pure interpretation.

Answer 1

The question, apparently, is completely off topic, since there is an asymptotic_complex tag ...

According to CLRS , p. 49,

"The number of anonymous functions in an expression is understood to be equal to the number of times an asymptotic notation appears. For example, in an expression

sum (O (i), i = 1..n)

there is only one anonymous function (function i). Thus, this expression does not match O (1) + O (2) + ... + O (n), which really does not have a clear interpretation "

Actually, in your formula the constants that lie behind the note O can be different, and their growth can change the asymptotic behavior of the whole sum. Do not write it!

---

To answer your question more fully, in the sum (O (i), i = 1..n), you can use the fact that (see GKP , p. 450 for the following)

O (f (n) g (n)) = f (n) O (g (n))

So O (i) = i O (1), this time with the same O (1) in your formula. Hence,

sum (O (i), i = 1..n) = sum (i, i = 1, n) O (1)

= n (n + 1) / 2 O (1) = O (n ^ 2)

Thus, you can easily get rid of your amount.

Answer 2

We turn to the definition of the Big-Oh notation.

You have n functions f_i , each of which satisfies

 a_i * i <= f_i(x) <= b_i * i; x > X_i 

for some positive constants a_i, b_i and sufficiently large X_i . let X = max_i ( X_i ) and sum over the inequalities n to get

 sum_i=1..n ( a_i * i ) <= sum_i=1..n ( f_i(x) ) <= sum_i=1..n ( b_i * i ) 

noting that

 sum_i=1..n ( min(a_i) * i ) <= sum_i=1..n ( a_i * i ) sum_i=1..n ( b_i * i ) <= sum_i=1..n ( max(b_i) * i ) 

arriving in

  min(a_i) * 0.5*(n(n-1)) <= sum_i=1..n ( f_i(x) ) <= max(b_i) * 0.5*(n(n-1)) <=> A * (n(n-1)) <= sum_i=1..n ( f_i(x) ) <= B *(n(n-1)) 

So the sum of the functions you started with is really O(n^2) .

Answer 3

Of course, O (1) and O (2) are constant, so we can forget about them. But O (n / 2) is constant, I think not. Therefore, try (for your homework) to count only the second half of the elements:

 O(n/2) + O(n/2+1) + ... O(n) = ?? 

you will find O(n^2) :)

Answer 4

There is a trick to find the formula, really not so difficult.

You have: 1 + 2 + 3 + 4 + .... + n

If you count the list twice (one time it was ordered from low to high once from high to low, you get twice as much result)

((1 + 2 + 3 + 4 + ... + n) + (n + (n - 1) + (n - 2) ... + 2 + 1)) / 2

This is the same as

((1 + n) + (2 + n - 1) + (3 + n - 2) + ... + (n + 1)) / 2

And this:

((n + 1) * n) / 2

or how we are right in the concept of O (n²).