Member Avatar for Member #682468

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
  • 482 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Member #682468

Dani AI

Generated

Short answer and a clean check: the total work is the arithmetic progression 1+2+...+n, so the growth is quadratic. A compact verification is to set f(n)=sum{i=1}^n i and compute the limit lim{n->infty} f(n)/n^2 = 1/2; that shows f(n) is Theta(n^2). This matches ’s point that the highest-degree polynomial term controls asymptotic behavior, and clarifies why ’s single-loop reading was misleading — as later noted, the algorithm has an outer loop and an inner scan that can be up to linear in n.

Practical note on getting Theta(n log n): the only way to drop from quadratic to n log n is to make the per-item inner work O(log n) instead of O(n). Common approaches:

  • keep the candidate sets in a balanced search structure (balanced BST / ordered set) so the “which set fits?” query is O(log n);
  • sort the input first and use binary-search or two-pointer greedy methods, yielding O(n log n) overall;
  • if the test is exact-match, use a hash table for amortized O(1) lookups (gives average-case linear time, but not guaranteed worst-case).

Example outline replacing the linear scan with a tree lookup:

for x in items:
    S = tree.find_best(x)    # O(log n)
    if S:
        S.add(x)             # O(log n) or O(1) amortized
    else:
        tree.insert(new_set(x))  # O(log n)

Caveat: to claim Theta(n log n) formally you need an O(n log n) algorithm plus consideration of lower bounds (many problems reducible to sorting have an Omega(n log n) comparison-based lower bound). Hashing gives faster average-case bounds but different worst-case guarantees.

Recommended Answers

All 4 Replies

Member Avatar for 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???

Edited by Taywin because: n/a
commented: The post was clear, helpful, and gave nice insight. +3
Member Avatar for Member #682468

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

Member Avatar for 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).

Edited by Rashakil Fol because: n/a
Member Avatar for Member #682468

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.