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?

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:

• Allocate array $p_1, p_2,\cdots, p_n$ of $n$ element in $E$.

• Let $s=e_1$, $p_1=1$

• For $i$ from 2 to $n-1$ inclusive, let $p_i = s$ and $s= se_i$.

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

-
Let $b=e_n$.

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

• 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.

StackExchange Computer Science Q#109216, answer score: 7