1
$\begingroup$

I am currently studying algorithms and computational complexity at University.

I have recently got through three questions I found in an old exam:

  1. Is it possible to sort in asymptotically linear time an array of rational numbers between $[1, 1.5]$ with limited numerator?

  2. Is it possible to sort in asymptotically linear time an array of rational numbers between $[0, 0.5]$ with limited numerator?

  3. Is it possible to sort in asymptotically linear time an array of rational numbers between $[0, 100]$ with limited denominator?

First of all I tried to understand what the author meant with "limited": I assumed it to be a synonym of "fixed" (i.e. a generic value $k$) and what comes below is based on this assumption.

As far as I know we can use three algorithms to achieve $O(n)$: counting sort, radix sort and bucket sort. In these questions no uniform distributions are guaranteed, so I basically ignored the last one.

For (1) I thought this: if all the numerators are the same ($k$), then we only have to sort all the elements by their denominator, in reverse order. Since the range is $[1, 1.5]$, the denominators must be an integer between $\left[\left\lceil\frac{2}{3}k\right\rceil, k\right]$. That is a limited interval of integers, so we can use counting sort and get $O(n)$. The answer is indeed "true", as stated in the solution.

For (2) I tried a similar approach: in this case we have a lower bound of $0$, so to reach it with a $k$ numerator we would need an infinite denominator. Since counting sort requires a finite range, we conclude that we can't get $O(n)$. The solution says "false", as I did.

For (3) we have a little difference but my intuition was to apply the same reasoning: if we set $k$ as denominator, then we must have a numerator in $[0, 100k]$ to fit within the original range. A fixed interval: we can apply counting sort! But the answer in the solution this time is "false", we do not sort in linear time.

The only other difference compared to (1) and (2) is the upper bound, which is higher. So, if we had a very large $k$, the range would be even larger and in $O(n + k)$ it would dominate over $n$. Anyway, I found another exam paper in which the range is completely removed, and the answer keeps to be marked as false.

I repeat: I based all of the above on the original assumption. I ask, therefore: was it wrong? Does "limited" have another meaning in this context? Or, more in general: why can't (3) be sorted in linear time, while (1) can?

Thanks in advance to everyone.

$\endgroup$

1 Answer 1

1
$\begingroup$

You can sort an array in linear time if the set of possible array elements is finite. Because in that case you just pick the array elements that have the smallest possible value, then the array elements that have the second smallest possible value, and so on. Each of these operations is linear in time, and there is a finite number of them, so the total time is linear.

The rational numbers between 0 and 0.5 with limited numerator are infinite. They contain for example the rational numbers 1/2, 1/3, 1/4, 1/5 ..., in general 1/n for all n >= 2. Plus many other rational numbers.

The rational numbers between 0 and 100 with limited denominator are finite. Let's say the limit for the denominator is K. Then we have the numbers i/1 for 1 <= i <= 100, exactly 100 of them. And the numbers i/2 for 1 <= i <= 200, exactly 200 of them, and eventually the numbers i/K for 1 <= i <= 100K, exactly 100K of those. There are roughly 100 * K^2 / 2 rational numbers in this set, so finite, so sorting can be done in linear time.

$\endgroup$
3
  • $\begingroup$ But the solution of the exam I found says we cannot order the third array in linear time $\endgroup$
    – Lorenzo
    Nov 13, 2023 at 7:43
  • $\begingroup$ Ask your teacher to post here. And if you answered that the third array can be sorted in linear time and get no points for that, I’ll be quite happy to tell them otherwise. $\endgroup$
    – gnasher729
    Nov 13, 2023 at 17:27
  • $\begingroup$ Here I am after a while... It was just a mistake in the (unofficial) solution paper, which wasn't written by the professor, but by a former student. Thank you anyway $\endgroup$
    – Lorenzo
    Dec 7, 2023 at 17:36

Your Answer

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

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