# 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 ...

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

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 ...

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, ...

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

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

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

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 ...

6

This is a standard geometric data structure problem, which can be solved by storing the intervals $(x_1, y_1), \dots, (x_n, y_n)$ in an interval tree. Then you can extract all the intervals $(x_i,y_i)$ overlapping a given query interval $(X,Y)$ in $O(\log n + k)$ time, where $k$ is the number of output intervals.

6

I don't have a definite answer to your question, but "braid sorting" seems a possible candidate. According to this wikipedia entry we can define it as follows. Let $X$ be a group, and let $H$ denote the set of tuples $(x_1,\ldots,x_n) \in X^n$ such that $x_1 \ldots x_n = 1_X$. If we let $G$ be the braid group $B_n$ generated by the moves $\sigma_i$, we can ...

6

This can be done by running all the $n!$ permutations in parallel and wait for one of them to output $1,2,6,24$ on inputs $1,2,3,4$. (Of course, that does not guarantee that you found the correct permutation for input 5.) Specific running time estimates may depend on the programming language being used. For instance, in BASIC each line is supposed to start ...

6

This is an open question even for one-dimensional point sets. In this setting, the distance-sorting problem is equivalent to sorting X+Y, where $X$ is the input set and $Y=-X$.

5

The Bentley-Saxe logarithmic method can sort a set in $O(n \lg n)$ time by merging sorted lists of equal size, much like merge sort.

5

No, such an algorithm cannot exist. Assume $t$ comparisons per element are allowed. For a start, consider the situation of merging two lists, one of size one, and the other of size $2^t$. There are $2^t+1$ possible results, and an easy adversarial argument shows that the element in the small list needs to participate in $t+1$ comparisons, and this element ...

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