0
$\begingroup$

Let A[1 : n] be a vector of n integers such that all elements except O(n^2/3) elements are between 1 and 10n. Design an algorithm with linear complexity that sorts A.

Beyond the algorithm, what I can't fully understand is why we are provided with the information "all elements except O(n^2/3)" It is certainly an information that guides the choice in some way of the algorithm. What considerations can we make on this information that is provided to us?. How can it guide us in choosing the best algorithm?

Improve this question
$\endgroup$
2
  • $\begingroup$ Presumably, you mean $n^{2/3}$ (which is a minority of elements). You can combine two types of sorts depending on whether the elements are in the given range or not. $\endgroup$
    – Yves Daoust
    Feb 14 at 9:19
  • $\begingroup$ This can work with any exponent less than one. $\endgroup$
    – Yves Daoust
    Feb 14 at 9:26

1 Answer 1

Reset to default
1
$\begingroup$

The reason you are provided that information is that, without this extra promise, it is not possible to sort in linear time. With this extra promise, it is possible to sort in linear time.

It's your exercise, so I will leave it to you to come up with the strategy to sort such an array in linear time. Once you've found such an algorithm, hopefully you will be able to see why the same can't be used on any array (without that promise).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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