Can't figure out $O(n \log n)$ divide and conquer algorithm 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.
