Algorithm $1\mathrm{.}4\mathrm{.}1$ If $xin{C}^n$ and $n=2^t,$ then this algorithm computes the discrete

Fourier transform $y=F_{n}x.$

function $y=fft(x,n)$

$ifn=1$

$y=x$

else

$m=\frac{n}{2}$

$y_T=fft(x(1$:$2$:$n),m)$

$y_B=fft(x(2$:$2$:$n),m)$

$=$exp$(-2\frac{i}{n})$

$d=[1,,$cdots,${}^{m-1}{]}^T$

$z=d****y_B$

$y=\left[\begin{array}{c}{y}_T+z\end{array}\right]$

$y_T-z$

end

P$1\mathrm{.}4\mathrm{.}1$ Suppose $w=[1,{}_n,{}_n^2,$dots,${}_n^{\frac{n}{2}-1}]$ where $n=2^t.$ Using the colon notation, express

$1,{}_r,{}_r^2,$dots,${}_r^{\frac{r}{2}-1}$

as a subvector of $w$ where $r=2^q,q=1$:$t.$ Rewrite Algorithm $1\mathrm{.}4\mathrm{.}1$ with the assumption that $w$ is

precomputed. Show that this maneuver reduces the flop count to $5n$logn$.$ Answer should be written in MATLAB