1
$\begingroup$

Suppose that the edge weights in a graph are uniformly distributed over the halfopen interval [0, 1).

The question is, how can one sort the edge weights in linear expected time?

I know the definition of expected time for inputs of size n is $\max_{I \in I_n} \sum_{R} P(R)T(I,R),$ where $I_n$ is the set of all inputs of size $n$ and $R$ denotes the random outcomes on which execution depends, which would be the edge weights in this case.

To sort in linear time, bucket sort would probably be useful.

Source: CLRS, Ch 23, exercise 23.2-6.

$\endgroup$
1
  • $\begingroup$ Does bucket sort work? $\endgroup$ Mar 9, 2022 at 8:41

1 Answer 1

1
$\begingroup$

Since your weights are reals, the answer probably depends on the specific model of computation that we are using. One strategy might be the following:

Select the first $\ell =3\log n$ bits in the binary representation of each number. In this way all the resulting (truncated) numbers will be distinct with high probability. Indeed, the probability that two fixed (truncated) numbers are the same is $2^{-\ell}$ and hence, the probability that there exists a pair of numbers that are the same is at most $n^2 2^{-\ell} = n^2 \cdot n^{-3} = n^{-1}$.

You can then multiply these numbers by $2^\ell$ to obtain integers between $0$ and $2^\ell = 2^{3 \log n} = n^3$. These integers can then be sorted in time $O(n)$ using radix sort.

This is a Monte-Carlo algorithm, i.e., there is a probability of at most $n^{-1}$ that the result will be incorrect. If this is undesirable then you can simply check (in $O(n)$ time) whether the resulting sequence of real numbers is sorted. If that's not the case, sort the reals using any $O(n^2)$-time algorithm. Since this only happens with probability at most $n^{-1}$, the overall contribution to the expected running time will be at most $O(n)$.

$\endgroup$
6
  • $\begingroup$ On numbers with $3 \log n$ bits, the radix sort may still take $O(n \log n)$. You should rather sort the values in $n$ buckets, each an interval $[k/n,(k+1)/n[$. Then the probability that any bucket receives $k$ values is less than $1/k!$, and the expected time to sort (using any $O(n^2)$ algorithm) the values in a bucket is O(1). $\endgroup$
    – Guyslain
    Mar 9, 2022 at 14:25
  • $\begingroup$ On numbers with $3\log n$ bits in the word-ram model, radix sort takes $O(n)$ time. Write all numbers in base $2^{\lfloor \log n \rfloor}$. Then each digit of each number fits in a word of ram and can be found in constant time (it's a contiguous group of bits). Moreover, each number has a constant number of digits. Therefore radix sort makes a constant number of iterations, each of which takes $O(n)$ time. $\endgroup$
    – Steven
    Mar 9, 2022 at 14:41
  • $\begingroup$ I understand now, thank you! $\endgroup$
    – Guyslain
    Mar 9, 2022 at 17:21
  • $\begingroup$ Thanks. But can you elaborate on why you can sort correctly in O(n) expected time? It's possible, though unlikely, that two real numbers with the first $\ell$ bits equal could be out of order and so, though unlikely, there's a chance that comparing those two real numbers can take a long time (at least if they're stored as infinite precision numbers). $\endgroup$ Mar 10, 2022 at 1:36
  • $\begingroup$ First of all let me clarify that I'm using $n$ to refer to the number of reals to sort (since these reals come from edge weights, there might be some confusion with the number of vertices in the graph). It's definitely possible that the sorting procedure fails, exactly because two real numbers might happen to agree on the first $\ell$ bits. However, we can detect this case in $O(n)$ time by checking whether the returned weights are sorted (I'm assuming that you can compare 2 reals in $O(1)$ time). If the procedure succeeds, which happens with probability at least $1-\frac{1}{n}$, you are done. $\endgroup$
    – Steven
    Mar 10, 2022 at 8:17

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.