If I have an array of 1 million integers. Summing it up is considered O(n) because I have to perfom n-1 add operations. Correct ?
+3
A:
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).
JoshD
2010-09-26 05:43:57
Calculating n*(n-1)/2 takes O(log n), not O(1).
Charles
2010-09-26 05:55:58
How do you figure? It's a few multiplications divisions and a subtraction. Regardless of n, it will take the same amount of time if there's no overflow.
JoshD
2010-09-26 06:00:35
It is O(1), if n was 1, it would take the same amount of time to calculate n*(n+1)/2 as when n would equal 1 million. Therefore it is not dependent on N: O(1) time [constant]
Bob Fincheimer
2010-09-26 06:06:31
No that is completely wrong. If he has an array of 1000000 entries then summing it up is O(1). It is only if he has an array of n entries that summing it up is O(n). (to clarify - your answer to the question, not the debate about n*(n-1)/2)
Amoss
2010-09-26 17:35:55
My assumption was that 1000000 was an example, and he's looking for the general case for n elements given that he stated n-1 additions.
JoshD
2010-09-26 17:51:35
@Bob, JoshD: I can calculate n*(n-1)/2 for n = 1 in about 5 nanoseconds. For n = 2^1000000, it takes 6,600,000 nanoseconds. Do you really want to argue that this is O(1)? n is about lg n bits, and n(n-1)/2 is about 2 lg n bits. It's hard to output 2 lg n bits in O(1).
Charles
2010-09-26 21:45:06
Actually, now that I think about it, it takes O((log n)^2) with schoolbook and O((log n)^(1 + epsilon)) with FFT-based methods.
Charles
2010-09-26 22:01:49
Damn! Why does the captcha always displays me barely readable image characters that takes at least three attempts to recognize for me and that delays my answer ?
Gopi
2010-09-26 05:48:05
A:
Yes, because the time used for summing is direct variation to the number of elements n.
tia
2010-09-26 06:37:47