For an $n$ that is a power of $2$, the $n × n$ Weirdo matrix $W_n$ is defined as follows. For $n = 1, W_1 = [1]$. For $n > 1$, $W_n$ is defined inductively by
$W_n = \left[ \begin{matrix} W_\frac{n}{2} & -W_\frac{n}{2} \\ I_\frac{n}{2} & W_\frac{n}{2} \\ \end{matrix} \right]$
where $I_k$ denotes the $k × k$ identity matrix. For example,
$W_2 = \left[ \begin{matrix} 1 & −1 \\ 1 & 1 \\ \end{matrix} \right]$, $W_4 = \left[ \begin{matrix} 1 & −1 & −1 & 1 \\ 1 & 1 & −1 & −1 \\ 1 & 0 & 1 & −1 \\ 0 & 1 & 1 & 1 \\ \end{matrix} \right]$, $W_8 = \left[ \begin{matrix} 1 & −1 & −1 & 1 & −1 & 1 & 1 & −1 \\ 1 & 1 & −1 & −1 & −1 & −1 & 1 & 1 \\ 1 & 0 & 1 & −1 & −1 & 0 & −1 & 1 \\ 0 & 1 & 1 & 1 & 0 & −1 & −1 & −1 \\ 1 & 0 & 0 & 0 & 1 & −1 & −1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & −1 & −1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 & −1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ \end{matrix} \right]$
How would I find a $O(nlogn)$ algorithm that calculates the product $W_n · \bar{x}$, where $\bar{x}$ is a vector of length $n$ and $n$ is a power of $2$?
I'm going to change indicies so that $W_n$ is a $2^n \times 2^n$ matrix. Let's assume that $x = (a, b)$ is a vector of length $2^n$, split up into two subvectors $a, b$ each of length $2^{n-1}$. Then we have that $$ W_n x = \begin{pmatrix} W_{n-1} & -W_{n-1} \\ I_{n-1} & W_{n-1} \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} W_{n-1} a - W_{n-1} b \\ a + W_{n-1} b \end{pmatrix} $$
Let $f(n)$ be the time needed to evaluate the product $W_n x$ for $x$ a vector of length $2^n$. Then the above computation shows that to compute $W_n x$, we need to compute the two products $W_{n-1} a$ and $W_{n-1} b$, and then do a linear amount of work to combine them. This is the same recurrence relation as merge-sort, and so we get an $O(n \log n)$ running time.