Para obter um aumento significativo na eficiência, é necessário que se decomponha a computação da DFT em computações sucessivamente menores.
Nesse processo exploram-se ambas a simetria e a periodicidade da exponencial complexa:
  Algoritmos nos quais a decomposição é baseada em um processo de decomposição da sequência x(n) em sequências sucessivamente menores são chamados algoritmos de decimação no tempo ("decimation-in-time" algorithms).

O princípio de decimação no tempo é mais bem ilustrado para o caso especial em que N é potência inteira de 2, i.e.:
  Como N é um inteiro par, é possível computar X(k) separando x(n) em duas subsequências de N/2 pontos cada, uma para a qual n é par e a outra para a qual n é ímpar. Assim, sendo X(k) dada por
 

(9)

tem-se
  Substituindo-se n par por n=2r e n ímpar por n=2r+1:
 

(10)

Como
  a equação (10) pode ser escrita como
 

(11)

Cada um dos somatórios na equação (11) corresponde a uma DFT de N/2 pontos, o primeiro correspondendo à DFT dos coeficientes de índice par da sequência x(n), e o segundo à DFT dos coeficientes de índice ímpar da sequência x(n). Apesar de k variar entre 0 e N-1, cada um dos somatórios só precisa ser computado para k variando do 0 a (N/2)-1, pois G(k) e H(k) são periódicas em k com período N/2. Após as duas DFT’s, correspondentes aos dois somatórios na equação (11) serem computadas, elas são combinadas para formar a DFT X(k).
A fig.3, reproduzida de Oppenheim e Schafer, Digital Signal Processing,1975., ilustra o método descrito acima para uma sequência de 8 pontos.
 

Figura 3

Com a computação reestruturada de acordo com a equação (11), pode-se comparar o número de multiplicações e adições requeridos com aqueles requeridos pelo cálculo direto da DFT. Anteriormente, foi visto que o cálculo direto requer N² multiplicações e adições complexas. Por comparação, a equação (11) requer o cálculo de duas DFT’s de N/2 pontos, as quais requerem 2(N/2)² multiplicações complexas e aproximadamente 2(N/2)² adições complexas. A combinação das 2 DFT’s requer N multiplicações complexas e N adições complexas, e logo a computação da equação (11) para todos os valores de k requer N + (N²/2) multiplicações complexas e adições complexas. Fica fácil verificar que para N>2, N + (N²/2) é menor que N².

A equação (11) corresponde a quebrar a computação da DFT original, de N pontos, em duas de N/2 pontos. Se N/2 for par, o que é sempre verdade se N for potência de 2, podemos computar a DFT de N/2 pontos quebrando cada somatório na equação (11) em duas DFT’s de N/4 pontos, as quais combinadas geram a DFT de N/2 pontos. Então G(k) e H(k) na equação (11) podem computadas como indicado abaixo:
  ou
 

(12)

Similarmente,
 

(13)

Assim, se as DFT’s de N/4 pontos forem calculadas de acordo com as equações (12) e (13) então tal cálculo deve ser feito como mostra a fig.4, aqui reproduzida de Oppenheim e Schafer, Digital Signal Processing,1975.
 

Figura 4

Substituindo o esquema indicado na fig.4 no diagrama de fluxo dado pela fig.3, obtém-se o diagrama de fluxo completo indicado na fig.5., também reproduzida de Oppenheim e Schafer, Digital Signal Processing,1975.

Para a DFT de 8 pontos que estamos utilizando como ilustração, o cálculo foi reduzido ao cálculo de DFT’s de 2 pontos. A fig.6, reproduzida aqui de Oppenheim e Schafer, Digital Signal Processing,1975, mostra o diagrama de fluxo da DFT de 8 pontos.

Para o caso mais geral onde N é uma potência de 2 maior que 3, pode-se proceder decompondo as transformadas de N/4 pontos nas equações (12) e (13) em transformadas de N/8 pontos, e continuar até que tenham-se somente transformadas de 2 pontos. Isto requer n rodadas de cálculos, onde n = log2 N .

Anteriormente foi visto que na decomposição original de uma transformada de N pontos em 2 transformadas de N/2 pontos, o número de multiplicações e adições complexas requeridas é N + 2(N/2) ². Quando as transformadas de N/2 pontos são decompostas em transformadas de N/4 pontos, o fator de (N/2) ² é substituído por N/2 + 2(N/4) ², e logo a computação completa requer N+N+2(N/4) ² multiplicações e adições complexas. Procedendo desta forma tantas vezes quanto possível, o número de multiplicações e adições complexas será igual a N log2N.
 

Figura 5

Figura 6