What is the computational cost of a radix-2 dit-fft

Question

1. Explain the decimation-in-frequency FFT algorithm using the matrix interpretation.

2. In the algebraic development of the DIT-FFT (or DIF-FFT) algorithm, two key steps are required at each stage. Explain those steps.

3. What is the computational cost of a radix-2 DIT-FFT algorithm? That of a radix-2 DIF-FFT algorithm?

4. Explain DIT and DIF FFT butterflies and their role in the FFT algorithms.