-2

I am studying an algorithm that in the worst case performs a number of operations like this:

N + (N -1) + (N - 2) + (N - 3) + ... + [N - (N -1)] + (N -N)

In the Big O notation analysis is this algorithm Linear, quadratic or something else?

Thank you very much.

5
  • 1
    What do you think? Give us some analysis.
    – Achrome
    Feb 7, 2013 at 10:23
  • It isn't a homework.. and sorry if the question is stupid. I found a good answer here : stackoverflow.com/questions/8261895/big-oh-notation
    – rdil2503
    Feb 7, 2013 at 10:27
  • that's a link to this post :)
    – UmNyobe
    Feb 7, 2013 at 10:29
  • Sorry :) I meant stackoverflow.com/questions/8261895/big-oh-notation
    – rdil2503
    Feb 7, 2013 at 10:31
  • For future reference, Wolfram|Alpha is your friend in these kinds of things.
    – Nuclearman
    Feb 7, 2013 at 19:14

2 Answers 2

6

This is math. Your sum is exactly equal to N*(N+1)/2

1
  • Thanks. After your answer i found this useful link stackoverflow.com/questions/8261895/big-oh-notation
    – rdil2503
    Feb 7, 2013 at 10:28
2

Your formula is the "small Gauss". It equals to n(n+1)/2.

Gauss' Trick equation

This is O( (n*n + n)/2 ) = O(n2)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.