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