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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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).