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
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???
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).
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).
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 :)
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.