4 ms·
"sum of the numbers from 1 to N is O(N^2)" Maybe I'm misunderstanding you, but no it isn't. it's O(N) if you have to traverse a list of numbers it's actually c
by gregors 13y ago
"sum of the numbers from 1 to N is O(N^2)"
Maybe I'm misunderstanding you, but no it isn't. it's O(N) if you have to traverse a list of numbers it's actually constant time if the numbers are sequential.
- aboveandbeyond 13y agoIt's actually O(1). It's (N * (N+1))/2
- gregors 13y agothat's what I said "constant time"
- Terr_ 13y agoYour post is missing some required punctuation which would've made that easier to see.
- randomthought 13y agowhat about (n(n+1)/2)< 1000 n^2 ? .
- thedufer 13y agoHe interpreted it as "the time complexity of computing the sum of the numbers from 1 to n", which using the formula you just gave takes O(1) time.
- ipince 13y agoNote that "sum of the numbers from 1 to N" is not the same as "summing the numbers from 1 to N".
- Dewie 13y agoThe fastest algorithm for computing the sum 1 + 2 + 3 + .. + n is constant. But the result of the sum is O(n^2). You can use that result to conclude that algorithms like for example bubble sort has a worst case running time of O(n^2), since it does (n-1) + (n-2) + ... + 1 swaps in the worst case during the whole sorting.