Aufgaben:Exercise 5.5Z: Complexity of the FFT - Revision history

Maintenance script: Fix interlanguage link: resolve redirect chain

2026-03-16T15:56:00Z

Fix interlanguage link: resolve redirect chain

← Older revision		Revision as of 17:56, 16 March 2026
Line 12:		Line 12:
	*Here  $w = {\rm e}^{-{\rm j}\hspace{0.05cm}\cdot \hspace{0.05cm} 2\pi/N}$  denotes the complex rotation factor.  For  $N = 8$  the value  $w = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} \pi/4} = \cos(45^\circ) - {\rm j} \cdot \sin(45^\circ)\hspace{0.05cm}$ is obtained.		*Here  $w = {\rm e}^{-{\rm j}\hspace{0.05cm}\cdot \hspace{0.05cm} 2\pi/N}$  denotes the complex rotation factor.  For  $N = 8$  the value  $w = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} \pi/4} = \cos(45^\circ) - {\rm j} \cdot \sin(45^\circ)\hspace{0.05cm}$ is obtained.
	*The exponent  $\mu$  for this complex rotation factor can take all integer values between  $0$  and  $N/2-1$.  For  $N = 8$  it is:		*The exponent  $\mu$  for this complex rotation factor can take all integer values between  $0$  and  $N/2-1$.  For  $N = 8$  it is:
	:$$w^0 = 1,\hspace{0.2cm}w^1 = {1}/{\sqrt{2}}- {\rm j}\cdot{1}/{\sqrt{2}},\hspace{0.2cm}w^2 = - {\~~rmj~~},\hspace{0.2cm}w^3 = -{1}/{\sqrt{2}}- {\rm j}\cdot{1}/{\sqrt{2}} \hspace{0.05cm}.$$		:$$w^0 = 1,\hspace{0.2cm}w^1 = {1}/{\sqrt{2}}- {\rm j}\cdot{1}/{\sqrt{2}},\hspace{0.2cm}w^2 = - {\rm j},\hspace{0.2cm}w^3 = -{1}/{\sqrt{2}}- {\rm j}\cdot{1}/{\sqrt{2}} \hspace{0.05cm}.$$

	The purpose of this task is to determine the number of arithmetic operations  $(\mathcal{O}_{\rm FFT})$  required for the FFT and compare it with the value  $\mathcal{O}_{\rm DFT} ≈ 8\cdot N^2$  that can be specified for the DFT.		The purpose of this task is to determine the number of arithmetic operations  $(\mathcal{O}_{\rm FFT})$  required for the FFT and compare it with the value  $\mathcal{O}_{\rm DFT} ≈ 8\cdot N^2$  that can be specified for the DFT.
Line 91:		Line 91:

	'''(6)'''  The computational time gain of the FFT over the conventional DFT is given by:		'''(6)'''  The computational time gain of the FFT over the conventional DFT is given by:
	:$$G_{\rm FFT} = \frac{\mathcal{O}_{\rm DFT}}{\mathcal{O}_{\rm FFT}} = \frac{8 \cdot N^2} {5 \~~cdotN~~ \cdot {\rm log_2}\hspace{0.1cm}N }= 1.6 \cdot \frac{N}{ {\~~rmlog_2~~}\hspace{0.1cm}N}$$		:$$G_{\rm FFT} = \frac{\mathcal{O}_{\rm DFT}}{\mathcal{O}_{\rm FFT}} = \frac{8 \cdot N^2} {5 \cdot N \cdot {\rm log_2}\hspace{0.1cm}N }= 1.6 \cdot \frac{N}{ {\rm log_2}\hspace{0.1cm}N}$$
	:$$\Rightarrow \hspace{0.3cm}G_{\rm FFT} \hspace{0.1cm}(N=16) = 1.6 \cdot\frac{16}{ 4} \hspace{0.15 cm}\underline{= 6.4}, \hspace{0.5cm}G_{\rm FFT} \hspace{0.1cm}(N=1024) = 1.6 \cdot\frac{1024}{ 10}\hspace{0.15 cm}\underline{ \approx 164}\hspace{0.05cm}.$$		:$$\Rightarrow \hspace{0.3cm}G_{\rm FFT} \hspace{0.1cm}(N=16) = 1.6 \cdot\frac{16}{ 4} \hspace{0.15 cm}\underline{= 6.4}, \hspace{0.5cm}G_{\rm FFT} \hspace{0.1cm}(N=1024) = 1.6 \cdot\frac{1024}{ 10}\hspace{0.15 cm}\underline{ \approx 164}\hspace{0.05cm}.$$

Line 100:		Line 100:

	[[Category:Signal Representation: Exercises\|^5.5 Fast Fourier Transform ^]]		[[Category:Signal Representation: Exercises\|^5.5 Fast Fourier Transform ^]]
	[[de:Aufgaben:5.~~5Z_Rechenaufwand_für_die_FFT~~]]		[[de:Aufgaben:Aufgabe 5.5Z: Rechenaufwand für die FFT]]

Maintenance script: Join split $$ formula lines for correct rendering

2026-03-16T13:48:52Z

Join split $$ formula lines for correct rendering

← Older revision		Revision as of 15:48, 16 March 2026
Line 12:		Line 12:
	*Here  $w = {\rm e}^{-{\rm j}\hspace{0.05cm}\cdot \hspace{0.05cm} 2\pi/N}$  denotes the complex rotation factor.  For  $N = 8$  the value  $w = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} \pi/4} = \cos(45^\circ) - {\rm j} \cdot \sin(45^\circ)\hspace{0.05cm}$ is obtained.		*Here  $w = {\rm e}^{-{\rm j}\hspace{0.05cm}\cdot \hspace{0.05cm} 2\pi/N}$  denotes the complex rotation factor.  For  $N = 8$  the value  $w = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} \pi/4} = \cos(45^\circ) - {\rm j} \cdot \sin(45^\circ)\hspace{0.05cm}$ is obtained.
	*The exponent  $\mu$  for this complex rotation factor can take all integer values between  $0$  and  $N/2-1$.  For  $N = 8$  it is:		*The exponent  $\mu$  for this complex rotation factor can take all integer values between  $0$  and  $N/2-1$.  For  $N = 8$  it is:
	:$$w^0 = 1,\hspace{0.2cm}w^1 = {1}/{\sqrt{2}}- {\rm j}		:$$w^0 = 1,\hspace{0.2cm}w^1 = {1}/{\sqrt{2}}- {\rm j}\cdot{1}/{\sqrt{2}},\hspace{0.2cm}w^2 = - {\rmj},\hspace{0.2cm}w^3 = -{1}/{\sqrt{2}}- {\rm j}\cdot{1}/{\sqrt{2}} \hspace{0.05cm}.$$
	\cdot{1}/{\sqrt{2}},\hspace{0.2cm}w^2 = - {\rm
	j},\hspace{0.2cm}w^3 = -{1}/{\sqrt{2}}- {\rm j}
	\cdot{1}/{\sqrt{2}} \hspace{0.05cm}.$$

	The purpose of this task is to determine the number of arithmetic operations  $(\mathcal{O}_{\rm FFT})$  required for the FFT and compare it with the value  $\mathcal{O}_{\rm DFT} ≈ 8\cdot N^2$  that can be specified for the DFT.		The purpose of this task is to determine the number of arithmetic operations  $(\mathcal{O}_{\rm FFT})$  required for the FFT and compare it with the value  $\mathcal{O}_{\rm DFT} ≈ 8\cdot N^2$  that can be specified for the DFT.
Line 69:		Line 66:
	{{ML-Kopf}}		{{ML-Kopf}}
	'''(1)'''  Each complex addition requires two real additions:		'''(1)'''  Each complex addition requires two real additions:
	:$$(R_1 + {\rm j} \cdot I_1) + (R_2 + {\rm j} \cdot I_2) = (R_1 +		:$$(R_1 + {\rm j} \cdot I_1) + (R_2 + {\rm j} \cdot I_2) = (R_1 +R_2) + {\rm j} \cdot (I_1 + I_2)\hspace{0.3cm}\Rightarrow \hspace{0.3cm}\hspace{0.15 cm}\underline{ A_{\rm A} =2}\hspace{0.05cm}.$$
	R_2) + {\rm j} \cdot (I_1 + I_2)\hspace{0.3cm}\Rightarrow \hspace{0.3cm}
	\hspace{0.15 cm}\underline{ A_{\rm A} =
	2}\hspace{0.05cm}.$$


	'''(2)'''  Any complex multiplication requires four real multiplications and two real additions:		'''(2)'''  Any complex multiplication requires four real multiplications and two real additions:
	:$$(R_1 + {\rm j} \cdot I_1) (R_2 + {\rm j} \cdot I_2) = (R_1 \~~cdot~~		:$$(R_1 + {\rm j} \cdot I_1) (R_2 + {\rm j} \cdot I_2) = (R_1 \cdotR_2 - I_1 \cdot I_2) + {\rm j} \cdot (R_1 \cdot I_2 + R_2 \cdotI_1)\hspace{0.3cm}\Rightarrow \hspace{0.3cm}\hspace{0.15 cm}\underline{A_{\rm M} = 2,\hspace{0.3cm}M_{\rm M} =4} \hspace{0.05cm}.$$
	~~R_2~~ - I_1 \cdot I_2) + {\rm j} \cdot (R_1 \cdot I_2 + R_2 \~~cdot~~
	~~I_1~~)\hspace{0.3cm}
	\Rightarrow \hspace{0.3cm}\hspace{0.15 cm}\underline{A_{\rm M} = 2,\hspace{0.3cm}M_{\rm M} =
	4} \hspace{0.05cm}.$$


Line 92:		Line 82:

	*Using the results of subtasks  '''(1)''',  '''(2)'''  and  '''(3)'''  we obtain for the total number of arithmetic operations:		*Using the results of subtasks  '''(1)''',  '''(2)'''  and  '''(3)'''  we obtain for the total number of arithmetic operations:
	:$$ \mathcal{O}_{\rm B} = a_{\rm B}\cdot A_{\rm A} + a_{\rm B}\cdot (A_{\rm M}		:$$ \mathcal{O}_{\rm B} = a_{\rm B}\cdot A_{\rm A} + a_{\rm B}\cdot (A_{\rm M}+M_{\rm M} ) = 2 \cdot 2 + 1 \cdot 6\hspace{0.15 cm}\underline{ = 10}\hspace{0.05cm}.$$
	+M_{\rm M} ) = 2 \cdot 2 + 1 \cdot 6\hspace{0.15 cm}\underline{ = 10}
	\hspace{0.05cm}.$$


	'''(5)'''  There are  ${\rm log_2} \ N$ stages in total, each of which requires  $N/2$  basic operations to be performed:		'''(5)'''  There are  ${\rm log_2} \ N$ stages in total, each of which requires  $N/2$  basic operations to be performed:
	:$$\mathcal{O}_{\rm FFT} = {\rm log_2}\hspace{0.1cm}N \cdot \frac{N}{2}\cdot		:$$\mathcal{O}_{\rm FFT} = {\rm log_2}\hspace{0.1cm}N \cdot \frac{N}{2}\cdot\mathcal{O}_{\rm B} = 5 \cdot N \cdot {\rm log_2}\hspace{0.1cm}N$$
	\mathcal{O}_{\rm B} = 5 \cdot N \cdot {\rm log_2}\hspace{0.1cm}N$$		:$$\Rightarrow \hspace{0.3cm}\mathcal{O}_{\rm FFT}\hspace{0.1cm}(N=16) = 5\cdot 16 \cdot4 \hspace{0.15 cm}\underline{= 320}, \hspace{0.5cm}\mathcal{O}_{\rm FFT}\hspace{0.1cm}(N=1024) = 5\cdot 1024\cdot 10 \hspace{0.15 cm}\underline{= 51200}\hspace{0.05cm}.$$
	:$$\Rightarrow \hspace{0.3cm}\mathcal{O}_{\rm FFT}\hspace{0.1cm}(N=16) = 5\cdot 16 \~~cdot~~
	4 \hspace{0.15 cm}\underline{= 320}, \hspace{0.5cm}\mathcal{O}_{\rm FFT}\hspace{0.1cm}(N=1024) = 5\cdot 1024
	\cdot 10 \hspace{0.15 cm}\underline{= 51200}
	\hspace{0.05cm}.$$


	'''(6)'''  The computational time gain of the FFT over the conventional DFT is given by:		'''(6)'''  The computational time gain of the FFT over the conventional DFT is given by:
	:$$G_{\rm FFT} = \frac{\mathcal{O}_{\rm DFT}}{\mathcal{O}_{\rm FFT}} = \frac{8 \cdot N^2} {5 \~~cdot~~		:$$G_{\rm FFT} = \frac{\mathcal{O}_{\rm DFT}}{\mathcal{O}_{\rm FFT}} = \frac{8 \cdot N^2} {5 \cdotN \cdot {\rm log_2}\hspace{0.1cm}N }= 1.6 \cdot \frac{N}{ {\rmlog_2}\hspace{0.1cm}N}$$
	N \cdot {\rm log_2}\hspace{0.1cm}N }= 1.6 \cdot \frac{N}{ {\rm		:$$\Rightarrow \hspace{0.3cm}G_{\rm FFT} \hspace{0.1cm}(N=16) = 1.6 \cdot\frac{16}{ 4} \hspace{0.15 cm}\underline{= 6.4}, \hspace{0.5cm}G_{\rm FFT} \hspace{0.1cm}(N=1024) = 1.6 \cdot\frac{1024}{ 10}\hspace{0.15 cm}\underline{ \approx 164}\hspace{0.05cm}.$$
	~~log_2~~}\hspace{0.1cm}N}$$
	:$$\Rightarrow \hspace{0.3cm}G_{\rm FFT} \hspace{0.1cm}(N=16) = 1.6 \cdot
	\frac{16}{ 4} \hspace{0.15 cm}\underline{= 6.4}, \hspace{0.5cm}G_{\rm FFT} \hspace{0.1cm}(N=1024) = 1.6 \cdot\frac{1024}{ 10}\hspace{0.15 cm}\underline{ \approx 164}
	\hspace{0.05cm}.$$

Maintenance script: Add German interlanguage link

2026-03-16T12:34:10Z

Add German interlanguage link

← Older revision		Revision as of 14:34, 16 March 2026
Line 120:		Line 120:

	[[Category:Signal Representation: Exercises\|^5.5 Fast Fourier Transform ^]]		[[Category:Signal Representation: Exercises\|^5.5 Fast Fourier Transform ^]]
			[[de:Aufgaben:5.5Z_Rechenaufwand_für_die_FFT]]

Guenter at 14:48, 24 May 2021

2021-05-24T14:48:25Z

← Older revision		Revision as of 16:48, 24 May 2021
Line 7:		Line 7:
	*The FFT occurs in  ${\rm log_2} \ N$  stages, whereby the exact same number of arithmetic operations must be carried out in each stage.		*The FFT occurs in  ${\rm log_2} \ N$  stages, whereby the exact same number of arithmetic operations must be carried out in each stage.
	*The diagram shows the third and last stage for the example  $N = 8$.  It can be seen that  $N/2$  basic operations have to be carried out in this and the other stages.		*The diagram shows the third and last stage for the example  $N = 8$.  It can be seen that  $N/2$  basic operations have to be carried out in this and the other stages.
	*In each basic operation called   '''butterfly''',  two complex outputs are calculated from the two complex input variables  $E_1$  and  $E_2$ :		*In each basic operation called  '''butterfly''',  two complex outputs are calculated from the two complex input variables  $E_1$  and  $E_2$ :
	:$$ A_1 = E_1 + E_2 \cdot w^{\hspace{0.04cm}\mu}, $$		:$$ A_1 = E_1 + E_2 \cdot w^{\hspace{0.04cm}\mu}, $$
	:$$ A_2 = E_1 - E_2 \cdot w^{\hspace{0.04cm} \mu}\hspace{0.05cm}.$$		:$$ A_2 = E_1 - E_2 \cdot w^{\hspace{0.04cm} \mu}\hspace{0.05cm}.$$

Guenter at 09:43, 22 May 2021

2021-05-22T09:43:35Z

Guenter at 08:34, 22 May 2021

2021-05-22T08:34:00Z

← Older revision		Revision as of 10:34, 22 May 2021
Line 26:		Line 26:
	*This task belongs to the chapter  [[Signal_Representation/Fast_Fourier_Transform_(FFT)\|Fast Fourier Transform (FFT)]].		*This task belongs to the chapter  [[Signal_Representation/Fast_Fourier_Transform_(FFT)\|Fast Fourier Transform (FFT)]].
	*It makes sense to calculate the powers of  $w$  before the actual algorithm and store them in a lookup table.  The operations necessary for this are to be disregarded.		*It makes sense to calculate the powers of  $w$  before the actual algorithm and store them in a lookup table.  The operations necessary for this are to be disregarded.
	*The bit reversal operation – a rearrangement that has to be carried out before the first stage – is also not to be taken into account in this estimation.		*The  "bit reversal operation"  – a rearrangement that has to be carried out before the first stage – is also not to be taken into account in this estimation.

Guenter at 08:33, 22 May 2021

2021-05-22T08:33:16Z

← Older revision		Revision as of 10:33, 22 May 2021
Line 4:		Line 4:

	[[File:P_ID1179__Sig_Z_5_5.png\|right\|frame\|Final step of the FFT for $N=8$]]		[[File:P_ID1179__Sig_Z_5_5.png\|right\|frame\|Final step of the FFT for $N=8$]]
	The FFT algorithm  (''Fast Fourier Transform'')  realises a  ''Discrete Fourier Transform''  with the smallest possible computational effort if the parameter  $N$  is a power of two. In detail, the following calculation steps are necessary to carry out an FFT:		The  $\rm FFT$  algorithm  ("Fast Fourier Transform")  realises a  "Discrete Fourier Transform"  $\rm (DFT)$  with the smallest possible computational effort if the parameter  $N$  is a power of two.  In detail, the following calculation steps are necessary to carry out an FFT:
	*The FFT occurs in  ${\rm log_2} \ N$  stages, whereby the exact same number of arithmetic operations must be carried out in each stage.		*The FFT occurs in  ${\rm log_2} \ N$  stages, whereby the exact same number of arithmetic operations must be carried out in each stage.
	*The diagram shows the third and last stage for the example  $N = 8$. It can be seen that  $N/2$  basic operations have to be carried out in this and the other stages.		*The diagram shows the third and last stage for the example  $N = 8$.  It can be seen that  $N/2$  basic operations have to be carried out in this and the other stages.
	*In each basic operation~~, which is often~~ called a   '''butterfly''' , two complex outputs are calculated from the two complex input variables  $E_1$  and  $E_2$ :		*In each basic operation called   '''butterfly''',  two complex outputs are calculated from the two complex input variables  $E_1$  and  $E_2$ :
	:$$ A_1 = E_1 + E_2 \cdot w^{\hspace{0.04cm}\mu}, $$		:$$ A_1 = E_1 + E_2 \cdot w^{\hspace{0.04cm}\mu}, $$
	:$$ A_2 = E_1 - E_2 \cdot w^{\hspace{0.04cm} \mu}\hspace{0.05cm}.$$		:$$ A_2 = E_1 - E_2 \cdot w^{\hspace{0.04cm} \mu}\hspace{0.05cm}.$$
	*Here  $w = {\rm e}^{-{\rm j}\hspace{0.05cm}\cdot \hspace{0.05cm} 2\pi/N}$  denotes the complex rotation factor. For  $N = 8$  the value  $w = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} \pi/4} = \cos(45^\circ) - {\rm j} \cdot \sin(45^\circ)\hspace{0.05cm}$ is obtained.		*Here  $w = {\rm e}^{-{\rm j}\hspace{0.05cm}\cdot \hspace{0.05cm} 2\pi/N}$  denotes the complex rotation factor.  For  $N = 8$  the value  $w = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} \pi/4} = \cos(45^\circ) - {\rm j} \cdot \sin(45^\circ)\hspace{0.05cm}$ is obtained.
	*The exponent  $\mu$  for this complex rotation factor can take all integer values between  $0$  and  $N/2-1$ . For  $N = 8$  it is:		*The exponent  $\mu$  for this complex rotation factor can take all integer values between  $0$  and  $N/2-1$.  For  $N = 8$  it is:
	:$$w^0 = 1,\hspace{0.2cm}w^1 = {1}/{\sqrt{2}}- {\rm j}		:$$w^0 = 1,\hspace{0.2cm}w^1 = {1}/{\sqrt{2}}- {\rm j}
	\cdot{1}/{\sqrt{2}},\hspace{0.2cm}w^2 = - {\rm		\cdot{1}/{\sqrt{2}},\hspace{0.2cm}w^2 = - {\rm
Line 17:		Line 17:
	\cdot{1}/{\sqrt{2}} \hspace{0.05cm}.$$		\cdot{1}/{\sqrt{2}} \hspace{0.05cm}.$$

	The purpose of this task is to determine the number of arithmetic operations  $(\mathcal{O}_{\rm FFT})$  required for the FFT and compare it with the value  $\mathcal{O}_{\rm DFT} ≈ 8\cdot N^2$  that can be specified for the DFT		The purpose of this task is to determine the number of arithmetic operations  $(\mathcal{O}_{\rm FFT})$  required for the FFT and compare it with the value  $\mathcal{O}_{\rm DFT} ≈ 8\cdot N^2$  that can be specified for the DFT.

	~~To be noted:~~
	*It makes sense to calculate the powers of  $w$  before the actual algorithm and store them in a lookup table.
	*The operations necessary for this are therefore to be disregarded.
	*The bit reversal operation – a rearrangement that has to be carried out before the first stage – is also not to be taken into account in this estimation.



Line 29:		Line 23:


	''~~Hint~~:''		''Hints:''
	*This task belongs to the chapter  [[Signal_Representation/Fast_Fourier_Transform_(FFT)\|Fast Fourier Transform (FFT)]].		*This task belongs to the chapter  [[Signal_Representation/Fast_Fourier_Transform_(FFT)\|Fast Fourier Transform (FFT)]].
			*It makes sense to calculate the powers of  $w$  before the actual algorithm and store them in a lookup table.  The operations necessary for this are to be disregarded.
			*The bit reversal operation – a rearrangement that has to be carried out before the first stage – is also not to be taken into account in this estimation.

Guenter: Guenter moved page Aufgaben:Exercise 5.5Z: Complexity of The FFT to Aufgaben:Exercise 5.5Z: Complexity of the FFT

2021-05-21T15:17:22Z

Guenter moved page Aufgaben:Exercise 5.5Z: Complexity of The FFT to Aufgaben:Exercise 5.5Z: Complexity of the FFT

← Older revision	Revision as of 17:17, 21 May 2021
(No difference)

Noah at 14:02, 23 March 2021

2021-03-23T14:02:03Z

Show changes

Javier: Text replacement - "Category:Exercises for Signal Representation" to "Category:Signal Representation: Exercises"

2021-03-23T12:38:57Z

Text replacement - "Category:Exercises for Signal Representation" to "Category:Signal Representation: Exercises"

← Older revision		Revision as of 14:38, 23 March 2021
Line 124:		Line 124:


	[[Category:~~Exercises for~~ Signal Representation\|^5.5 Fast Fourier Transform ^]]		[[Category:Signal Representation: Exercises\|^5.5 Fast Fourier Transform ^]]

← Older revision		Revision as of 11:43, 22 May 2021
Line 44:		Line 44:
	$M_{\rm M} \hspace{0.2cm} = \ $ { 4 }		$M_{\rm M} \hspace{0.2cm} = \ $ { 4 }

	{How many complex additions/subtractions  $(a_{\rm B})$  does a single basic operationn (&~~bdquo~~;butterfly&~~rdquo~~;) require?		{How many complex additions/subtractions  $(a_{\rm B})$  does a single basic operationn  ("butterfly")  require?
	<br>How many complex multiplications  $(m_{\rm B})$  are required per basic operation?		<br>How many complex multiplications  $(m_{\rm B})$  are required per basic operation?
	\|type="{}"}		\|type="{}"}
Line 54:		Line 54:
	$\mathcal{O}_{\rm B} \ = \ $ { 10 }		$\mathcal{O}_{\rm B} \ = \ $ { 10 }

	{How many real operations  $(\mathcal{O}_{\rm FFT})$  does the entire FFT–algorithm require? What are the values for  $N = 16$  und  $N = 1024$?		{How many real operations  $(\mathcal{O}_{\rm FFT})$  does the entire FFT–algorithm require?  What are the values for  $N = 16$  und  $N = 1024$?
	\|type="{}"}		\|type="{}"}
	$N = 16\text{:} \hspace{0.65cm} \mathcal{O}_{\rm FFT} \ = \ $ { 320 3% }		$N = 16\text{:} \hspace{0.65cm} \mathcal{O}_{\rm FFT} \ = \ $ { 320 3% }
	$N = 1024\text{:} \hspace{0.2cm} \mathcal{O}_{\rm FFT} \ = \ $ { 51200 3% }		$N = 1024\text{:} \hspace{0.2cm} \mathcal{O}_{\rm FFT} \ = \ $ { 51200 3% }

	{What is the time gain  $G_{\rm FFT} = \mathcal{O}_{\rm DFT} - \mathcal{O}_{\rm FFT}$  ~~für~~  $N = 16$  and  $N = 1024$?		{What is the time gain  $G_{\rm FFT} = \mathcal{O}_{\rm DFT} - \mathcal{O}_{\rm FFT}$  for  $N = 16$  and  $N = 1024$?
	\|type="{}"}		\|type="{}"}
	$N = 16\text{:} \hspace{0.65cm} G_{\rm FFT} \ = \ $ { 6.4 3% }		$N = 16\text{:} \hspace{0.65cm} G_{\rm FFT} \ = \ $ { 6.4 3% }