sort an array where $0\leq a_n\leq n$
sort an array where $0\leq a_n\leq n^2$(hint represent every element in base $n$)
All the elements are integers
for the first 1 I used counting sort and for the second one I thought maybe after changing to base $n$ using raddix? ONe more thing,i've been asked to prove correctness for this first 1 but I've never see how to do this.
Any hints?

  • $\begingroup$ Does the problem say $0\leq a_n\leq n$ or rather $0\leq a_k\leq n$, for $k=1,2,...,n$? $\endgroup$ – plop Nov 14 '20 at 16:21
  • $\begingroup$ (The hint in the second part is a giveaway, rather.) $\endgroup$ – greybeard Nov 14 '20 at 16:58

You can make a list of length $n^k$ which $k$ is $1$ for the first case and $2$ for the second one.

So you have an array and you can put each element in the relevant position. This idea may waste space but it's fast.

Time complexity of this algorithm is $O(n)$.

Space Complexity is $O(n^k)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.