3
$\begingroup$

I have a sorted array $A$ of non-arbitrary elements. Now, I have another element $c$ and I want to find out where it belongs in the sorting of $A$. The cost of comparing $c$ to $A_i$ is $\Theta(i^2)$. I do not directly care about the number of comparisons, I just want to minimize the sum of the costs of the comparisons in the expected case (worst-case would also be nice).

Let's assume that each element in $A$ is unique and that $A$ does not contain $c$.

What is the optimal algorithm?

$\endgroup$
  • $\begingroup$ Optimal in what sense? $\endgroup$ – Yuval Filmus Jul 24 '18 at 16:59
  • 1
    $\begingroup$ @YuvalFilmus "to minimize the sum of the costs of the comparisons" $\endgroup$ – koverman47 Jul 24 '18 at 17:02
  • $\begingroup$ Can your element $c$ belong to $A$? Or does $c$ belong to one of the $|A|+1$ intervals created by removing the elements of $A$? Or perhaps, $c$ necessarily belongs to $A$? $\endgroup$ – Yuval Filmus Jul 24 '18 at 17:03
  • $\begingroup$ $c$ could belong to $A$, but I have only binary comparison. Either $c \geq A_i$ or $c < A_i$. I want to find the $i$ where $c \geq A_i$ and $c < A_{i+1}$. Also, it is given that $c \geq A_0$ and $c < \max(A_i)$. $\endgroup$ – Albert Hendriks Jul 24 '18 at 20:59
  • $\begingroup$ Actually $c$ belongs to $A$, but by my previous comment we can only find its index $i$ by comparing $c$ to both $A_i$ and $A_{i+1}$. $\endgroup$ – Albert Hendriks Jul 24 '18 at 21:11
3
$\begingroup$

Let's say I told you in advance that $c$ is in the larger half. You still need $\Omega(\log n)$ comparisons, while now every helpful comparison takes $\Omega(n^2)$ cost, so the cost is always $\Omega(n^2\log n)$, which can be achieved with simple binary search.

$\endgroup$
1
$\begingroup$

@Willard Zhan explains the asymptotic complexity.

If you want to optimize the constant factor, you can work out the optimal schedule of queries using dynamic programming. Let $B[i,j]$ denote the worst-case cost of the optimal strategy when $c$ is already known to be in the range $A[i]...A[j]$, and let $\text{cost}(i)$ denote the cost of comparing $c$ to $A[i]$. Then we have the recursive relation

$$B[i,k] = \min\{\text{cost}(j) + \max(B[i,j-1], B[j+1,k]) : j=i,i+1,i+2,\dots,k\}$$

with the base case that $B[i,k] = 0$ if $i \ge k$. The $B$ array can be filled in using dynamic programming, and from that you can compute the strategy whose worst-case cost is minimal. You can use a similar strategy ot compute the strategy whose expected cost is minimal; you just have to adjust the recursive relation above (the specific relation will depend on your assumptions on the distribution of $c$).

See also https://cstheory.stackexchange.com/q/40996/5038.

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