Calculating all products of $n-1$ factors when given $n$ factors

Let's assume we have an operator $$\times: E^2\to E$$ of which we merely know that it is associative. Let's say a multiplication $$e\times f$$ always takes up a time of $$M$$ for all $$e, f\in E$$.

We're now given $$n$$ elements $$e_1,...,e_n\in E$$, and are tasked to calculate all $$n$$ products $$\def\bigtimes{\mathop{\vcenter{\huge\times}}} p_j :=\bigtimes_{i=1\\i\neq j}^n e_i$$

Naively multiplying out all $$n$$ products takes $$O(n^2M)$$.

A more sophisticated approach that runs in $$O(n^{3/2}M)$$ splits $$\bigtimes_{i=1}^n e_i$$ at arbitrary positions into $$\sqrt n$$ factors.
For each of the $$n$$ products, we now only have to recalculate one factor, and multiply the resulting factor, and the other $$k-1$$ factors together.

What is the fastest algorithm for this problem, and how does it look like?

• You can use divide and conquer to calculate $p_1$ in $O(n)$-time, and store the resulting divide-and-conquer result. When calculating the $p_2...p_n$, you can partition each chain product into $O(\log(n))$ range product queries to the stored divide-and-conquer tree of the first product, and use associativity to merge the queries. This takes $O(\log n)$ time when calculating $p_i$, which leads to an $O(n \log n \cdot M)$ overall time bound. Pretty sure you can do a little better. As an alternative, look at data structures for range sum/product queries and Fenwick trees. – BearAqua May 11 '19 at 3:11

Here is the fastest algorithm. I bet. The idea of the algorithm can be seen from the one-line explanation between step 4 and step 5 below.

Input: $$e_1,\cdots,e_n\in E$$, where $$n\ge 3$$.
Output: $$p_1, \cdots, p_n$$, where $$p_j=e_1\cdots e_{j-1}e_{j+1}\cdots e_n$$, the product of all input elements except $$e_j$$.
Procedure:

1. Allocate array $$p_1, p_2,\cdots, p_n$$ of $$n$$ element in $$E$$.
2. Let $$s=e_1$$, $$p_1=1$$
3. For $$i$$ from 2 to $$n-1$$ inclusive, let $$p_i = s$$ and $$s= se_i$$.
4. Let $$p_n=s.$$

Now $$\begin{pmatrix} p_1\\p_2\\ p_3\\p_4\\\cdots\\ p_{n-1}\\ p_n \end{pmatrix} \text{is} \begin{pmatrix} 1\\e_1\\e_1e_2\\ e_1e_2e_3\\\cdots\\ e_1e_2\cdots e_{n-2}\\e_1e_2\cdots e_{n-2}e_{n-1} \end{pmatrix}$$.

5. Let $$b=e_n$$.

6. For $$i$$ from $$n-1$$ to 2 inclusive downwards, let $$p_i=p_ib$$ and $$b = e_ib$$.
7. Let $$p_1=b$$.

The number of multiplications performed by the algorithm above is $$3(n-2)$$.

I believe that is the tight lower bound. However, I have not been successful proving it even though I have tried a few times. I am still trying from time to time.

• What a nice and clean algorithm! I was expecting there'd be an $O(n\log n)$ algorithm - that associativity without commutativity would be enough to reach $O(n)$ is ... pretty cool, to be honest. – Sudix May 11 '19 at 16:40
• Nice, elegant and concise. +1'd – lox May 12 '19 at 14:25