Theta Complexity of the sum of all numbers below n

[joehms22]

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

[Taywin]

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???

[joehms22]

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

[Rashakil Fol]

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

[joehms22]

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 :)