0
sum = 0;
   for (int i = 0; i < N; i++)
      for (int j = i; j ≥ 0; j--)         
         sum++;

I found out the big-oh to be O(n^2) but I am not sure how to find the theta bound for it. Can someone help?

NewProgrammer7
  • 33
  • 1
  • 6
  • This might help http://stackoverflow.com/questions/10376740/what-exactly-does-big-%D3%A8-notation-represent – Atri Jan 14 '16 at 20:38
  • Hi @NewProgrammer7. If the answer below has solved your question please consider [accepting it](http://meta.stackexchange.com/q/5234/179419) by clicking the check-mark. This indicates to the wider community that you've found a solution and gives some reputation to both the answerer and yourself. There is no obligation to do this. If you don't think the answer solves your question, consider giving feedback or updating your question with more details. – dfrib Jan 26 '16 at 13:02

1 Answers1

0

You can make use of sigma notation to derive asymptotic bounds for your algorithm:

enter image description here

Since we can show that T(n) O(n^2) (upper asymptotic bound) as well as in Ω(n^2) (lower asymptotic bound), it follows that T(n) is in Θ(n^2) ("sandwiched", upper and lower asymptotic bound).

In case it's unclear: note that the inner and out sums in the initial expressions above describe your inner and outer for loops, respectively.

dfrib
  • 70,367
  • 12
  • 127
  • 192