Explanation of pseudocode and time complexity analysis

Question

I am trying to work my way through some computer science training and I am not able to properly understand the following pseudo code:

COUNTING-1 (n) cost times
1 for r=1 to n c1 n+1
2 for c=1 to n c2 n(n+1)
3 sum = sum+1 c3 n2
4 return sum c4 1
T(n)=c2*n(n+1)+c3*n2 +c1*(n+1)+c4=an2+bn+c

Could someone explain why the outer loop is n+1, and not just n?

Also what are the constants c, a and b? I don't understand why they need to factor into the explanation equation as it isnt clear what their value will.

Apologies if these are really simple questions. If there are some useful things I should read I would appreciate a pointer in the right direction.

*Edit: I think looking at it again the c constant is the cost of the operation which for each is constant time, so 1. Is the cost of a single operation ALWAYS 1? If it is (which it appears to be in this RAM model) what is the point in over complicating the formula underneath with those values?

Why not just T(n)=n(n+1) + n2 + (n+1)

• greybeard: (Not "the loop" is "+1": the control expression is evaluated once for every trip, +1 for "done: no more trips".)
• pac234: Ah ok so this means the counter would increment one more time, however the body of the loop would not execute that final time?

Answer 1

First question: some book, for example well known CLRS 3ed. p25-26, counts, that in for loop test in loop header is executed one times more, then loop body. Accordingly you see $n^2=n(n+1)-n$ in 3-d line.

Second question: simplify $T(n)$ and write it as polynomial from $n$. Then you obtain representations for $a,b,c$: $$T(n)=c_2n(n+1)+c_3n^2 +c_1(n+1)+c_4=\\=(c_2+c_3)n^2+(c_2+c_1)n+(c_1+c_4)=\\=an^2+bn+c$$

So $a=(c_2+c_3)$, $b=c_2+c_1$ and $c=c_1+c_4$. If we speak about asymptotic estimation, then $T(n)=O(n^2)$.

• pac234: Have you got a link to what you did to get to the simplified form in your second point? I get the first poiint now, thanks. I still dont understand how you arrived at the simplified form (I thought we would drop C1, C2 etc) and just end up with n2. I still cannot understand exactly what c1... are or a,b,c and its making it really hard for me to move on with anything else.
• pac234: Ok I think I get most of it now, so they are the terms in that polynomial meaning it is quadratic (correct me if I am wrong). Would you mind explaining or linking to how you simplified the left hand side?
• zkutch: Added some more details. For simplification open brackets and join members with equal power. Feel free to ask more if/when you'll need it.