Time complexity of optimization problem

Question

Since I'm very new to complexity theory, I was hoping someone can give me some advices/hints on the following problem.

Suppose we know the values of $x_i$, $i=1,2,3,...,n$. How do we choose an integer $k$ such that $\sum_{i=1}^{k} (k-n)x_i$ is minimized; $0 \leq k \leq n$?

I think the problem is $O(n)$ time complexity and I'm trying to see if I can develop an algorithm that can improve its efficiency.

Answer 1

It's clearly $O(n)$, for here's an algorithm:

Set S(0) = 0, min = S(0), minIndex = 0;

For i = 1 to n:

Compute S(i) = (i-n) * [S(i-1)/((i-1)-n) +  x_i];
If S(i) < min:
   Set min = S(i) and minIndex = i; 

return minIndex;

There's really no hope for improving the efficiency, because there's a sequence $\{x_i\}$ with the property that an alteration to any particular item $x_j$ will make the result be $j$. Thus to determine the answer, you must at least examine each $x_i$, which takes time $\Omega(n)$.

I wonder, however, whether the sum was supposed to be $$ \sum_{i=1}^k (i-n) x_i $$ for if not, the $k-n$ just factors out of the sum, so it's peculiar to write it inside.

Post-comment addition

OP asks for a sequence with the property that by altering $x_i$, I can make the result be $i$. Let's look at $n = 4$, since that case completely illustrates what I'm going to say. I'm going to pick a sequence of $x_i$ values -- all zeroes! -- and we'll see what the five possible sums are:

$k = 0$ gives $0$

$k = 1$ gives $(1-4) \cdot 0 = -3 \cdot 0 = 0$

$k = 2$ gives $(2-4) \cdot 0 = -2 \cdot 0 = 0$

$k = 3$ gives $(3-4) \cdot 0 = -1 \cdot 0 = 0$

$k = 4$ gives $(4-4) \cdot 0 = 0 \cdot 0 = 0$.

Now I have to admit that I cannot, by changing $x_4$, alter that last sum, so what I said was no quite true. But by changing any of the other $x_i$, I can make the sum be largest at $i$. For instance, if I change $x_2$ to be $-1$, I get this:

$k = 0$ gives $0$

$k = 1$ gives $(1-4) \cdot 0 = -3 \cdot 0 = 0$

$k = 2$ gives $(2-4) \cdot -1 = -2 \cdot -1 = 2$

$k = 3$ gives $(3-4) \cdot -1 = -1 \cdot -1 = 1$

$k = 4$ gives $(4-4) \cdot -1 = 0 \cdot -1 = 0$.

See what happened there? Similarly, I could instead leave $x_2 = 0$ and change $x_3$ to be $-1$. Then I'd get

$k = 0$ gives $0$

$k = 1$ gives $(1-4) \cdot 0 = -3 \cdot 0 = 0$

$k = 2$ gives $(2-4) \cdot 0 = -2 \cdot 0 = 0$

$k = 3$ gives $(3-4) \cdot -1 = -1 \cdot -1 = 1$

$k = 4$ gives $(4-4) \cdot -1 = 0 \cdot -1 = 0$.

And I could do the same thing for $x_1$. There's a final gotcha: I can't make any adjustment that'll make $k = 0$ be the winner.

But in general, starting with a sequence in which all elements except the $i$th are zero, and the $i$th is $-1$, yields (for $i = 1, 2, \ldots, n-1$) a result in which the optimal sum occurs at $i$. Since the only way to distinguish this "has a 1 in some slot" sequence from the "all zero" sequence is to examine every element, the time need is proportional to $n-2$, which is $O(n)$.