Running time of a nested for loop

1a.)The loop is below and I want to find it's running time. Here is the loop

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

The first for loops runs in O(n) which is easy, however for the 2nd I think it also runs in O(n)开发者_开发问答 time because whenever j = i, this loop will run i times.

So I wrote down this has a running time of O(n^2).

1b. )Moreover, can someone also explain what is meant, when a problems asks for a "theta bound"?

---

Well, it's pretty simple to work out the exact number of loop iterations here. You get 1 + 2 + 3 + 4 + 5 + 6 + 7 + ... + N.

That sums to N(N+1) / 2, so yes, the algorithmic complexity is O(N²).

I can't say I've come across theta bounds... the Wikipedia page on big-O notation mentions it though, so that might be a reasonable starting point.

---

Theta bound means that it is a tight asymptotic bound, that bounds the running time both from above and below. In your example, N^2 is both a lower and upper bound on the running time, and hence it is a theta bound on the running time.

More formally:

there exists k1 and k2 such that:

N^2 * k1 <= N(N+1)/2 <= N^2 * k2

for N > some value N0.

Ps. This book gives a pretty good explanation of the different asymptotic bounds: http://www.amazon.com/Introduction-Algorithms-Third-Thomas-Cormen/dp/0262033844/ref=sr_1_1?ie=UTF8&qid=1295777605&sr=8-1

---

f(n) = O(g(n)) if and only if for big enough n there exists a constant c such that f(n) <= c*g(n). Basically, big-O notation gives you an upper bound. You could just as well say your program runs in O(n^3), O(n^2011) and even O(n^42142342), but these wouldn't be of much help to you, would they?

Theta notation gives you a tight bound, which is a lot more helpful. f(n) = Theta(g(n)) if and only if for big enough n there exists constants c1, c2 such that c1*g(n) <= f(n) <= c2*g(n), which means that you know the exact function your algorithm is proportional to.

Your algorithm does 1 + 2 + 3 + ... + N operations, which sums up to N(N+1)/2. This is Theta(N^2) because N^2/4 + N/4 <= N^2/2 + N/2 <= N^2 + N. So you can take c1 and c2 in the above definition to be 1/2 and 2.

Most of the time people will use big-O notation to express a tight bound, but this is not necessary. There are always multiple answers when asked for the big-O of a function, but only one answer when asked for the theta bound.