Lessons from a Silicon Valley job search

Re:Lessons from a Silicon Valley job search by gregors on Wednesday March 19, 2014 @12:22PM (#7429726)

"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.

[ Parent | on HN ]

Re:Lessons from a Silicon Valley job search by ipince on Wednesday March 19, 2014 @01:09PM (#7430155)

Note that "sum of the numbers from 1 to N" is not the same as "summing the numbers from 1 to N".

[ Parent | on HN ]

Re:Lessons from a Silicon Valley job search by aboveandbeyond on Wednesday March 19, 2014 @12:41PM (#7429886)

It's actually O(1). It's (N * (N+1))/2

[ Parent | on HN ]

Re:Lessons from a Silicon Valley job search by gregors on Wednesday March 19, 2014 @12:54PM (#7430030)

that's what I said "constant time"

[ Parent | on HN ]

Re:Lessons from a Silicon Valley job search by Terr_ on Wednesday March 19, 2014 @02:42PM (#7430794)

Your post is missing some required punctuation which would've made that easier to see.

[ Parent | on HN ]

Re:Lessons from a Silicon Valley job search by randomthought on Wednesday March 19, 2014 @07:07PM (#7432503)

what about (n(n+1)/2)< 1000 n^2 ? .

[ Parent | on HN ]

Re:Lessons from a Silicon Valley job search by thedufer on Thursday March 20, 2014 @12:03AM (#7433785)

He 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.

[ Parent | on HN ]

Re:Lessons from a Silicon Valley job search by Dewie on Wednesday March 19, 2014 @03:37PM (#7431210)

The 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.

[ Parent | on HN ]