Evaluate $\prod_{k=1}^{n} \sum_{i\ =1}^{k} a_i$ in $\mathcal{O}(n)$

Question

Write a Matlab program, which takes the vector $(a_1, \ldots, a_n)$ and outputs $\prod_{k=1}^{n} \sum_{i\ =1}^{k} a_i$. You are only allowed to define two variables and have to solve the problem in $\mathcal{O}(n)$.

I am pretty sure this is closely related to Horner's method, but I haven't been able to simplify the expression for small $n$ into a form that looked like Horner:

For $n = 3$ we have \begin{align} \prod_{k=1}^{3} \sum_{i = 1}^{k} a_i & = a_1^3 + 2a-1^2+a^2 + a_1 a_2^2+ a_1^2 a_3 + a_1 a_2 a_3 \\ & = a_1(a_1(a_1 + a_2(2 + a_2) + a_3) + a_2 a_3). \end{align}

Any help is appreciated :)

Answer 1

Do you consider the following to be $\mathcal{O}(n)$ steps?:

start: x = 0; p=1;

for k = 1 to n do

begin

$$x = x + a_k \quad ;\\ p = p\cdot x \quad; $$

end

The result is p.