Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
@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$).
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.
