Click here to Skip to main content
15,347,383 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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

1 solution

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).
   
Comments
Maciej Los 27-Nov-19 9:08am
   
Sounds reasonable ;)
This might be helpful too: Complexity of an algorithm[^]

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900