Big O estimate for summing up an array

If I have an array of 1 million 开发者_C百科integers. Summing it up is considered O(n) because I have to perfom n-1 add operations. Correct ?

---

If you can add two elements in O(1) then summing n elements takes O(n), yes. If they may take longer, then no. For example, if all of the elements are unsigned 32-bit integers but you want the exact sum (not the sum mod 2³²) then it may be as large as n · (2³² − 1) in which case summing will take O(n log n).

---

Yes. That's exactly correct.

Of course, there may be special cases where it's less. And certain methods could make it smaller, but those methods have a greater overhead than addition.

For example, if you know the values are from 1 to n, that's O(1) because you can compute n*(n+1)/2. But the general case is O(n).

---

Yes, because the time used for summing is direct variation to the number of elements n.