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.