1
$\begingroup$

Suppose x is a vector of size N with positive real elements sorted in decreasing order. Is it possible to find the analytical solution (no iterative solution) to the optimum value of M (1<= M <= N) whether $$M \log \left(1+\frac{M}{\sum_{i=1}^M \frac{1}{x_i}}\right)$$ is maximized?

$\endgroup$

1 Answer 1

1
$\begingroup$

The naive method of just evaluating $$f(M) = M\log\left(1+\frac{M}{\sum_{i=1}^M\frac{1}{x_i}}\right)$$ is an $O(N)$ algortithm. Since one can, by choosing $$x_N = 1 \\ x_{N-k} = 1+(k-1)\epsilon \text{ when } n-k > m_0 \\ x_{N-k} = k+1 \text{ when } n-k \geq m_0 \\ $$ with $\epsilon$ sufficiently small always adjust the $\{x_i\}$ such that to the optimum value of $M$ is at the arbitrarily chosen $m_0$, there can be no algorithm that is better than $O(N)$ (that is, no "not-iterative" solution).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.