15,347,383 members
See more:
How are you? Greetings to all of you. I have a task and that is to find the complexity of the counting algorithm sort line by line to finally find the T(n). The truth is that it has been quite a complicated subject for me, but I have been working on this so I would like to know if someone with knowledge of this can tell me if it is right or wrong. the pseudocode:

What I have tried:

```..............................cost..............repetitions
for i = 1 to k do...................2.....................k+1
c[i] = 0 ...................... ....1..................... k
for j = 1 to n do ..................2 .....................n+1
c[A[j]] = c[A[j]] + 1...............2..................... n
for i = 2 to k do.............. ....2 .....................k+2
c[i] = c[i] + c[i-1] ...............2 ..................... k
for j = n-1 down to 1...............2..................... n+1
B[ c[A[j]]] = A[j]..................1 ..................... n
c[A[j]] = c[A[j]] - 1.........,.....2 ..................... n```

therefore t(n)= 2k+2+k+2n+2+2n+2k+4+2k+2n+2+n+n

T(n)=7k+8n+8

I'm not really sure about this analysis but it's the best I could do :v. thank you for any suggestion
I have investigated that the complexity is O(n+k) but I need to know which is its (T(n)) to later find c1,c2 and No for the average case and better, so I do the analysis line by line if you give me something like T(n)=2n+4k for example
Posted
Updated 26-Nov-19 21:21pm
v2

## Solution 1

Provided the loops are not nested, your final result is correct, in my opinion. Since
```for i = 1 to k do  // k * const
c[i] = 0
for j = 1 to n do   // n * const
c[A[j]] = c[A[j]] + 1
for i = 2 to k do // (k-1) * const
c[i] = c[i] + c[i-1]
for j = n-1 down to 1 // (n-1) * const
B[ c[A[j]]] = A[j]
c[A[j]] = c[A[j]] - 1```

That makes complexity go with `(2*n*const)`, that is `O(n)`.
Maciej Los 27-Nov-19 9:08am

Sounds reasonable ;)
This might be helpful too: Complexity of an algorithm[^]