4 ms·
Why is summing a list of numbers 1 to N O(N^2) instead of O(N), don't you just iterate through the set of numbers once? EDIT: Nevermind, I think it means the v
by utnick 13y ago
Why is summing a list of numbers 1 to N O(N^2) instead of O(N), don't you just iterate through the set of numbers once?
EDIT: Nevermind, I think it means the value of the sum is on the order of n^2
- gregors 13y agoThe size of the number (result) is (N(N + 1))/2, the computation of the algorithm is constant. I've never heard anyone discuss the result of the algorithm using Big O.
- gvb 13y agoI think he meant factorial rather than sum. The sum of the numbers is O(1) - you can calculate it algorithmically. N*(N+1)/2 Ref: http://www.wikihow.com/Sum-the-Integers-from-1-to-N http://www.wikihow.com/Sum-the-Integers-from-1-to-N
- gregors 13y agohttps://math.stackexchange.com/questions/195924/proving-a-factorial-is-not-a-certain-complexity https://math.stackexchange.com/questions/195924/proving-a-fa...