$k = \Theta(n)$
The arrays consist only natural numbers $1$ to $n$
The sum of the length of all arrays = $\Theta(n)$
It should return the $k$ original arrays, each sorted on its own.
The running time should be at worst $\Theta(n)$. How is it even possible? There's something I must be missing because I have no idea how to approach this. The data I gave you is all the given data. Any ideas?
Using counting sort on each array won't work, for it will be $\Theta(n^2)$, but maybe a different approach using this method?