Thread: Asymptotic help needed

Say you have a fuction for any non negative whole number, whereby it equals

n + (n-1) + (n-2) + (n-3) + ... + (1)

I'm trying to represent this as an asymptotic answer, is anyone able to point me in the right direction?

Originally Posted by Wiretron

Say you have a fuction for any non negative whole number, whereby it equals

n + (n-1) + (n-2) + (n-3) + ... + (1)

I'm trying to represent this as an asymptotic answer, is anyone able to point me in the right direction?

n + (n-1) + (n-2) + (n-3) + ... + (1) = n(n+1)/2

as n becomes large n becomes negligable compared to n^2 so:

n + (n-1) + (n-2) + (n-3) + ... + (1) = n(n+1)/2 = (n^2)/2 +n/2 ~ (n^2)/2,

or in big-O notations:

..................................................= O(n^2).

RonL