4
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – BearAqua May 11 at 3:11
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Sudix May 11 at 16:40
  • $\begingroup$ Nice, elegant and concise. +1'd $\endgroup$ – lox May 12 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.