0
$\begingroup$

In the comparison sort model of sorting, the fastest possible algorithm is order $n \log(n)$, where $n$ is the number of input numbers. What is the time complexity of sorting a list of natural numbers, each represented as a string of ones and zeros, and separated by commas. For example, the input $11,1,10$ would be sorted as $1,10,11$.

Here is a more precise definition of the function.

Consider the following function: $f:S\to S$ where $S$ is the set of all finite strings over the alphabet containing three symbols, $0$, $1$ and 'comma', where $f$ is defined by interpreting each sub string starting and ending in a comma as an integer. If such a subtring starts with some zeros, ignore them. Then $f$ sorts these integers and returns a new string formed by representing each integer in the sorted list as a binary string and inserting commas between them. To further clarify the definition of $f$, here is a python script which defines $f$.

def f(s):
    # if the input is not a string over the alphabet "01," then return an empty output
    if type(s) != str or False in [t in ['0','1',','] for t in s]: return ''
    # convert the string to a list of integers and sort it
    L = sorted([int(t,2) for t in s.split(',')])
    # convert back to a bit string seperated by commas and return this
    return ','.join([f"{l:>b}" for l in L])

print(f('111,10,1,01111'))
# this outputs:
#   1,10,111,1111

Let $n$ denote the length of the input string, that is, the number of ones zeros and commas. I'd like to know the big omega time complexity of this function $f$ in terms of $n$. Please note that I do not mean to ask what the time complexity of the particular implementation of the function I defined above is, but rather the time complexity of the best possible implementation.

$\endgroup$
13
  • $\begingroup$ What are your thoughts? Why do you think the answer would be any different for this specific way of encoding the input? What's the fastest algorithm you can come up with? If there was an algorithm to solve your problem efficiently, can you think of any cool way to use that algorithm to do something you wouldn't otherwise be able to do? $\endgroup$
    – D.W.
    Sep 21 at 23:29
  • $\begingroup$ You might as well ask what is the time complexity to sort numbers in unary representation, if you believe the representation affects the algorithm complexity. $\endgroup$
    – Rinkesh P
    Sep 22 at 4:24
  • $\begingroup$ The lower bounds are based on the number of comparisons required to place the elements in the right order. Knowing this, think about whether there is any difference in comparing two numbers when their representation is changed to a different base. $\endgroup$
    – Michel
    Sep 22 at 20:57
  • $\begingroup$ Quicksort does not sort require $O(n \log n)$ time (in the worst case). $\endgroup$
    – Steven
    Sep 22 at 22:08
  • 1
    $\begingroup$ Please specify whether you want a comparison sort on these binary numbers and whether you allow for restrictions on the inputs or require the binary numbers to be sorted to be general. The answer depends on these. Your question is too vague in it's current form. $\endgroup$
    – Michel
    yesterday

2 Answers 2

2
$\begingroup$

Assuming there are $n$ numbers, and each number can be represented in $O(\log n)$ bits, you can read in the file and each number in $O(n \log n)$ time, then sort with any standard comparison-based sort algorithm, for a total running time of $O(n \log n)$.

If each number is $m$ bits long, and there are $n$ numbers, then it can take $O(nm)$ time just to read in the input, so if $m \gg \log n$, then there is no hope for a $O(n \log n)$ time algorithm. In such a case, a better measure of running time is to measure the running time in terms of the length of the input. Let $N=nm$ be the length of the input. Then it is easy to read in the input in $O(N)$ time, and then sort it using a comparison-based sort in $O(N \log N)$ time, for a total running time of $O(N \log N)$ time, where $N$ is the length of the input.

$\endgroup$
2
  • 1
    $\begingroup$ That's actually quite an interesting problem. If the input size is N bits, then you might have O(N) very small numbers that can be sorted in O(n) using counting sort. If the numbers are huge, say N^(1/3) bits, then you have O(N^(2/3)) numbers that can be sorted with O(N^(2/3) log N) comparisons. O (N) sorting might be possible. $\endgroup$
    – gnasher729
    yesterday
  • 1
    $\begingroup$ A bad case would be N = 10^9, a million numbers, each 1000 bits, and each number 980 fixed bits plus a number from 1 to 1,000,000. 1,000,000 numbers so 10^6 * 20 comparisons, each comparison takes 1,000 steps because the first 980 bits are equal, so the work for the comparisons is N log N. As Ray Butterworth says, O(N) should be possible but you need to use fewer full comparisons than Quicksort in this case. $\endgroup$
    – gnasher729
    yesterday
2
$\begingroup$

If there are N numbers, M is the number of bits in the longest number, and you have enough memory available to hold 2 copies of the data, a radix sort would be of linear order O(M×N).

New contributor
Ray Butterworth is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$

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.