We're a community of 1.1M IT Pros here for help, advice, solutions, professional growth and fun. Join us!
1,080,617 Members — Technology Publication meets Social Media

# Theta Complexity of the sum of all numbers below n

I've got an algorithm that at most does 1 operation for the first time a loop is run, 2 for the second, 3 for the third up to n for the nth.

Essentially the sum of all numbers 1 to n is the worst case running time. or [TEX]\frac{n*(n+1)}{2}[/TEX] I can't seem to figure out how to translate this to theta notation though.

I think it is just [TEX]\theta(cn)[/TEX] is that correct? If not, why?

Thanks,
Joe

3
Contributors
4
Replies
1 Day
Discussion Span
1 Year Ago
Last Updated
5
Views
Question
joehms22
Junior Poster
114 posts since Jan 2010
Reputation Points: 28
Skill Endorsements: 0

In my opinion, it should be BigTheta(n^2) still. If we take a look at the average case time complexity equation, it becomes (n^2+n)/2. The upper bound is O(n^2) for sure and the lower bound is BigOmega(n). If you are talking about Big Theta of an average case, the value which is multiply with "n" is still not a constant. So I don't think that it is correct to replace "n^2" with "cn" in your Big Theta notation. Therefore, it is still n^2.

Wait... If you are talking about sum of all numbers below n, the equation shouldn't be (n*(n+1)/2)??? Where did you get this??? When you do the summation, you go through each number once. The number of operation inside a loop is a constant, not a variable. Therefore, it should still be "n" instead???

Taywin
Posting Maven
2,633 posts since Apr 2010
Reputation Points: 275
Skill Endorsements: 17

In my opinion, it should be BigTheta(n^2) still. If we take a look at the average case time complexity equation, it becomes (n^2+n)/2. The upper bound is O(n^2) for sure and the lower bound is BigOmega(n). If you are talking about Big Theta of an average case, the value which is multiply with "n" is still not a constant. So I don't think that it is correct to replace "n^2" with "cn" in your Big Theta notation. Therefore, it is still n^2.

Wait... If you are talking about sum of all numbers below n, the equation shouldn't be (n*(n+1)/2)??? Where did you get this??? When you do the summation, you go through each number once. The number of operation inside a loop is a constant, not a variable. Therefore, it should still be "n" instead???

Cool, thanks, these things were still just confusing me a little. My equation came from Gauss' supposed solution to adding numbers 1 - 100. You are correct that I am not just using a single loop, I'm actually using a loop inside a loop. The external loop will run n times, the internal one will iterate through an array of sets, looking for a suitable one to place n inside, if it isn't found, a new set is created and added to the list, therefore for each n there are at most n-1 sets to look at for a suitable solution (under my reasoning).

joehms22
Junior Poster
114 posts since Jan 2010
Reputation Points: 28
Skill Endorsements: 0

Taywin is basically incredibly confused.

If your algorithm does n^2/2 + n/2 operations then its running time is Theta(n^2).

As a general rule the polynomial a*n^k + b*n^(k-1) + ... + c*n^0 is Theta(n^k).

In particular, (1/2)*(n^2) <= n^2/2 + n/2 <= n^2, for all n >= 1. (Can you prove this yourself?) This by definition means that the function taking n to n^2/2 + n/2 is in Theta(n^2).

Edit:
You could also say that your formula n*(n+1)/2 is Theta(n*(n+1)/2). This is never incorrect. Of course the idea is to simplify it, since Theta(n^2) = Theta(n*(n+1)/2).

Rashakil Fol
Super Senior Demiposter
Team Colleague
2,732 posts since Jun 2005
Reputation Points: 1,153
Skill Endorsements: 25

Taywin is basically incredibly confused.

If your algorithm does n^2/2 + n/2 operations then its running time is Theta(n^2).

As a general rule the polynomial a*n^k + b*n^(k-1) + ... + c*n^0 is Theta(n^k).

In particular, (1/2)*(n^2) <= n^2/2 + n/2 <= n^2, for all n >= 1. (Can you prove this yourself?) This by definition means that the function taking n to n^2/2 + n/2 is in Theta(n^2).

Edit:
You could also say that your formula n*(n+1)/2 is Theta(n*(n+1)/2). This is never incorrect. Of course the idea is to simplify it, since Theta(n^2) = Theta(n*(n+1)/2).

Thanks that clears everything up nicely, I was told the best version of the algorithm I was building would have Theta(n*lg(n)), so I guess I'll keep searching :)

joehms22
Junior Poster
114 posts since Jan 2010
Reputation Points: 28