0
$\begingroup$

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)

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

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – pac234
    Commented Nov 17, 2020 at 14:53
  • $\begingroup$ 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? $\endgroup$
    – pac234
    Commented Nov 17, 2020 at 15:00
  • $\begingroup$ 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. $\endgroup$
    – zkutch
    Commented Nov 17, 2020 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.