Fast Walsh–Hadamard transform

In computational mathematics, the Hadamard ordered fast Walsh–Hadamard transform (FWHT_h) is an efficient algorithm to compute the Walsh–Hadamard transform (WHT). A naive implementation of the WHT of order ${\displaystyle n=2^{m}}$ would have a computational complexity of O(${\displaystyle n^{2}}$). The FWHT_h requires only ${\displaystyle n\log n}$ additions or subtractions.

The FWHT_h is a divide and conquer algorithm that recursively breaks down a WHT of size ${\displaystyle n}$ into two smaller WHTs of size ${\displaystyle n/2}$. This implementation follows the recursive definition of the ${\displaystyle 2^{m}\times 2^{m}}$ Hadamard matrix ${\displaystyle H_{m}}$:

...
Wikipedia