2
$\begingroup$

Given a permutation $P$ of an unknown array $U$ of length $N$ and a function $f(Q)$ that calculates the minumum number of swaps between consecutive elements of array $Q$ to reach $U$, what is the minimum number of invocations of $f$ to discover $U$, worst case?

An upper bound of $N$ invocations is at hand:

Calculate $F(P)$, then for each $i,2\le i\le N$ move $P_i$ to the start of array $P$, then calculate $f(P)$ to discover the correct position of $P_i$ in subarray $P_{1...i}$. Being a little more careful, we can spare the last calculation of $f(P)$ since having $P_{1...N-1}$ ordered and knowing $f(P)$ is enough to calculate the correct position of $P_N$.

This yields the upper bound of $N-1$ invocations

For an array with length $2$, is clear that we need at least one invocation so this is a tight bound.

Question: For a sufficiently large $N$, is it possible to do less than $N-1$ invocations of $f$ in the worst case?.

Asymptotically, since the possible outputs of $f$ are $0...N(N-1)/2$ by the pidgeonhole principle we need at least $O(\log_{N(N-1)/2}(N!))=O(\log_N(N!))=O(N)$ (by Stirling's approximation) invocations to discover the array $P$. So this prompts a second question:

Question: For a sufficiently large $N$, is it possible to do less than $c\times N$ invocations of $f$ for some constant $c<1$ in the worst case?.

$\endgroup$
  • 1
    $\begingroup$ You can use Stirling's approximation to make your information-theoretic bound more precise. There are $N!$ permutations, so it takes $\lg N!$ bits to specify them. By Stirling's approximation, $\lg N! = N \lg N - 1.44 N + O(\lg N)$, so for sufficiently large $N$, we have $\lg N! \ge N \lg N - 1.44 N$. Now each query gives you $\lg(N^2/2) \le 2 \lg N$ bits of information. Therefore, you will need at least $(N \lg N - 1.44 N) / 2 \lg N$ queries, or in other words, at least $N/2 - 0.72N/\lg N$ queries. $\endgroup$ – D.W. May 26 '18 at 18:37
  • 1
    $\begingroup$ So, you can't expect to solve this in $cN$ queries if $c<0.5$. This leaves open the question of what is achievable in the range $0.5 \le c \le 1$. $\endgroup$ – D.W. May 26 '18 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.