Determine the number of exor operations

Question

Response to the following:

Discuss complexity of calculation of the Boolean difference of a function of n variables by FFT-like algorithms and through decision diagrams.

Illustrate the considerations by the example of functions f₁ and f₂ defined by the truth-vectors

F₁ = [1,0,0,1,0,1,1,1]^T,

F₂ = [1,0,0,0,0,1,0,1]^T,

and determine the number of EXOR operations required in FFT-like algorithms and decision diagram methods.