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:
........................................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
