Algorithme

On utilise un tableau pour représenter la matrice d'une fonction f de $\ensuremath{\matheu{F}}(m)$ dans la base $\ensuremath{\matheu{B}}$, l'algorithme est alors récursif sur les indices de tableaux :

let hadamard f=
  let g=copy_vect f in
  let rec hadam j n=
    for k=0 to n-1 do
      let aux=g.(j+k) in
      g.(j+ k )<-aux + g.(j+k+n);
      g.(j+k+n)<-aux - g.(j+k+n)
    done;
    if n>=2 then (
      hadam   j   (n/2);
      hadam (j+n) (n/2)
    ) in
  hadam 0 (vect_length f / 2);
  g;;

En notant $c(i)$ le nombre d'additions et de soustractions de complexes effectuées lors de l'appel à hadam avec $n=2^i$, on a $c(0)=2$, et $c(i)=2 \times 2^i+2 \times c(i-1)$ si $i\geq1$,

$$\frac{c(i)}{2^i}=2+\frac{c(i-1)}{2^{i-1}}$$

$$\frac{c(i)}{2^i}=(i+1) \times 2 i=0$$

Le nombre d'additions et de soustractions de complexes est donc $m \times 2^m$.