# Explanation of pseudocode and time complexity analysis

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)

• (Not "the loop" is "+1": the control expression is evaluated once for every trip, +1 for "done: no more trips".) Commented Nov 17, 2020 at 6:47
• Ah ok so this means the counter would increment one more time, however the body of the loop would not execute that final time? Commented Nov 17, 2020 at 7:04

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