Saludos a todos ustedes. Tengo un trabajo y es encontrar la complejidad del algoritmo counting sort línea por línea para finalmente encontrar la T(n). La verdad es que ha sido un tema bastante complicado para mí, pero he estado trabajando en ello, así que me gustaría saber si alguien con conocimiento de esto puede decirme si está bien o mal. el pseudocodigo:
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 downto 1 do 2 n+1
B[ c[A[j]]] = A[j] 1 n
c[A[j]] = c[A[j]] - 1 2 n
Por lo tanto t(n)= 2k+2+k+2n+2+2n+2k+4+2k+2n+2n+2+n+n
T(n)=7k+8n+8
No estoy muy seguro de este análisis, pero es lo mejor que he podido hacer :v. Gracias por cualquier sugerencia.
(Me tomé el atrevimiento de corregir, cuando se hace algoritmia se deben cerrar los ciclos, es solo convención) cuando implementas puedes ofuscar el código con estas sentencias las cuales el compiler de igual forma te cambia.