# Tag Info

24

Preprocess the array of $n$ values in time $O(n)$: $i\leftarrow n$ while $i>2$ Compute the median $m$ of $A[1..i]$ in time $O(i)$ partition $A[1..i]$ into $A[1..i/2-1] \leq m$ and $A[i/2+1..i]\geq m$ in the same time. $i \leftarrow \lfloor i/2 \rfloor$ The total precomputation time is within $O(1+2+4+...+n)\subseteq O(n)$ Answer a query for the $k$ ...

24

I think your question was addressed in Beigel and Gill's paper "Sorting n objects using k-sorter" from 1990 and the abstract of the paper says it all: A k-sorter is a device that sorts k objects in unit time. The complexity of an algorithm that uses a k-sorter is defined as the number of applications of the k-sorter. In this measure, the complexity of ...

17

Upon discussing this with Michael T. Goodrich, it seems that the parallel sorting algorithm by Cole for EREW PRAM does the job. See Richard Cole: "Parallel Merge Sort". SIAM J. Comput. 17(4): 770-785 (1988). In that algorithm there are $O(\log n)$ rounds and in each round each element participates in $O(1)$ comparisons. (One has to understand the algorithm ...

17

Kenneth Oksanen has published an expanded table of values up to $n=15$, based on his own computer search. Okansen also provides descriptions of the optimal comparison trees for most of the values he reports. Here's a screenshot of his table: Thanks to @MarkusBläser for the lead!

16

It's possible to sort with $O(\sqrt n\log n)$ calls to the black box and no comparisons. First, consider the following balanced partitioning problem: given $m$ elements $A[1..m]$ (where $\sqrt n \le m \le n$), partition them into two groups, the smallest of size at least about $m/4$, so that all elements in the first group are smaller than all elements in ...

16

How do you decide what the "wrong way" is? Take the first wrong-way swap gate, and interchange the two wires going out of it (including all their associated gates) so that it's correct. This doesn't change the fundamental circuit. It may introduce more wrong-way swap gates, but they're all later in the circuit. Now, you can keep doing this until you've ...

15

The lower bound is correct (2) - you can not do this better than $\Omega(n^2 \log n)$ and (1) is of course wrong. Lets us first define what is a sorted matrix - it is a matrix where the elements in each row and column are sorted in increasing order. It is now easy to verify that each diagonal might contains elements that are in any arbitrary order - you ...

14

Assume for simplicity that $n = 2^m$. Use the linear time selection algorithm to find the elements at positions $2^{m-1},2^{m-2},2^{m-3},\ldots,1$; this takes linear time. Given $k$, find $t$ such that $2^{t-1} \leq k \leq 2^t$; note that $2^t \leq 2k$. Filter out all elements of rank at most $2^t$, and now use the linear time selection algorithm to find the ...

13

Goodrich's "Randomized Shellsort: A Simple Oblivious Sorting Algorithm" has a discussion of data-oblivious sorting. Sorting networks are data-oblivious, but impractical in general, as I understand it.

13

You can't sort it in linear time. Suppose you have $n$ items, and you divide them into $\sqrt{n}$ consecutive blocks of $\sqrt{n}$ items each. You need to take $\sqrt{n} \log \sqrt{n}$ comparisons to sort each one. And there are $\sqrt{n}$ of them, giving $\theta(n \log n)$ time total. And it's easy to see that there can't be more than $n^{3/2}$ ...

12

It is possible to sort obliviously with $O(\sqrt{n}\log n)$ calls to the black box, each applied to a contiguous subarray of the original input. The algorithm never touches the input data except through black-box calls. In particular, the same sequence of black-box calls is only a function of $n$, not the actual input data (hence "oblivious"). Here is a ...

11

Ok, so as I understand it, you are given as input an undirected graph (representing the "within range" restrictions) with weights on its vertices, and you want to find a non-adjacent pair of vertices that has maximum total weight. I'm going to interpret linear time as being linear in the number of edges in the input graph, not just the number of vertices, ...

11

If you allow me to give an answer that uses "technical" terminology: the output of a finite state transducer on any given regular language is again a regular language. The sort of regular $(ab)^*$ equals non-regular $\{ a^nb^n \mid n\ge 0\}$. Thus that cannot be performed by a FST. (added) The fact that regular languages are closed under FST is a ...

10

EDIT (UPDATE): The lower bound in my answer below was proven (by a different proof) in "On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees", by Das et al; Algorithmica 19:447-460 (1997). is it possible to achieve even an approximation ratio like $O(n^{1-\epsilon})$ for some $\epsilon>0$ in $o(n\log n)$ time ...

10

We can compute $m$ in linear time. For simplicity suppose that the arrays are 0 based: $A[0..n-1]$, $B[0..n-1]$. We want to compute $m = \max_i B[i]+i$. Let $max = \max_i A[i]$. Obviously $max \leq m$. Let $A[j]$ be $B[k]$ after sorting. If $A[j] \leq max - n$ we have B[k] + k \leq B[k] + (n-1) = A[j] + (n-1) \leq (max-n) + (n-1) = max-1 < max \leq ...

9

I think this problem is NP-hard. I try to sketch a reduction from MinSAT. In the MinSAT problem we are given a CNF and our goal is to minimize the number of satisfied clauses. This problem is NP-hard, see e.g., http://epubs.siam.org/doi/abs/10.1137/S0895480191220836?journalCode=sjdmec Divide the vertices into two groups - some will represent literals, the ...

9

Suppose you have $n$ numbers $x_1,\ldots,x_n$ of width $m \geq \log n$. Without loss of generality, all numbers are different (add an extra $\log n$ lower-order bits). Two numbers can be compared in AC0, so in AC0 we can compute, for each $x_i$, a binary vector $v$, defined by $v_j = 1$ if $x_j \geq x_i$. In TC0 we can sort $v$ to $w$, and then locate (in ...

9

Your problem is solved in the paper Spheres of Permutations under the Infinity Norm — Permutations with limited displacement by Torleiv Kløve. See also A002524 and other sequences linked there. I found Kløve's paper by calculating the first few values of A002524 and finding it on the OEIS.

9

It seems unlikely to me for information-theoretic reasons. Expressing the answer to a sorting problem requires $\Omega(n\log n)$ bits of information. On the other hand, the answer to a maximum flow problem on an $m$-edge graph can be expressed (via a network simplex formulation) using only $O(m)$ bits of information (which edges are saturated, which are ...

9

I found the result hidden in an obscure 4p technical report: I share my results here in case others are interested. Knuth mentions runs in his description of "natural merge sort" (page 160 of the tome 3 of the 3rd edition), but he analyzes its complexity only on average (which yields n/2 runs), not in function of the number ρ of runs in 1985, Mannila proved ...

9

Your problem is known under the name MINIMUM DIRECTED BANDWIDTH. It is NP-complete: M.R. Garey, R.L. Graham, D.S. Johnson and D.E. Knuth: "Complexity Results for Bandwidth Minimization" SIAM Journal on Applied Mathematics 34, (1978), pp. 477-495 It is problem [GT41] in the NP-completeness book by Garey and Johnson. The special case where every ...

8

There is a sort algorithm with $O(1)$ auxiliary words and achieving $O(n\log n)$ worst-case run time, where $n$ is the length of the input array. http://www.springerlink.com/content/d7348168624070v7/ I don't think that the question seeks an algorithm with $O(1)$ auxiliary bits, because such algorithm must be tricky. I mean, if we cannot use even $O(\log n)$...

8

It seems not. Ian Parberry makes reference to a paper by Chung and Ravikumar, where they supposedly give a recursive construction of a sorting network that sorts every bitstring but one, and further deduce that the problem of verifying a sorting network is $co$-$NP$ complete. I can't find the original paper right away, but certainly it matches (my) ...

8

This is a topic of "adaptive sorting." As a starter, see the wikipedia page https://en.wikipedia.org/wiki/Adaptive_sort . It is known that we can sort a sequence of length $n$ with $k$ inversions with $O(n \log (2+k/n))$ comparisons. When $k=O(n^{3/2})$, this translates to $O(n \log n)$. We also have a lower bound of $\Omega(n \log (2+k/n))$. Thus, we know ...

8

$O(n)$ space with $O(\log k/\log \log n+\log \log n)$ query time is possible. See this paper.

8

This sounds a lot like the ASort algorithm. See this article by Giesen et. al.: https://www.inf.ethz.ch/personal/smilos/asort3.pdf Unfortunately, the running time is not quite linear. The article above proves that any comparison-based randomized algorithm ranking $n$ items within $n^2/\nu(n)$ has a lower bound of $n*log (\nu(n))$ (assuming $\nu(n) < n$)....

7

Unfortunately, the problem is NP-hard in general, according to Amir, Hartman, Kapah, Levy and Porat (see http://epubs.siam.org/doi/abs/10.1137/080712969), even if each symbol appears at most three times. I didn't find a mention of a constant factor approximation algorithm, or of something reasonably fast to tackle the problem. Are there any additional ...

7

No, bitonic sort is not stable. For this post I will denote numbers as 2;0 where only the part before the ; is used for comparison and the part behind ; to mark the initial position. Comparison-exchanges are denoted by arrows where the head points at the desired location of the greater value. As written in the link that @JukkaSuomela posted a stable ...

6

It is not possible to sort an arbitrary string with a fixed size transducer. For simplicity, let's say you are working over the alphabet $\{0,1\}$, where $0<1$. Proof: assume by way of contradiction that there exists such a transducer $A$ with $n$ states. Consider the input $1^{n+1}0$. Since $A$ has $n$ states, it must repeat a state before it finishes ...

6

Yes there is. The best known deterministic algorithm in linear space runs in time within $O(n\lg\lg n)$ and was presented by Han in 2004. The best known randomized algorithm in linear space runs in time within $O(n\sqrt{\lg\lg n})$ and was presented by Han and Thorup in 2012. For more details, see the section on "Trans-dichotomous algorithms" from the ...

Only top voted, non community-wiki answers of a minimum length are eligible