Question:
Number of 2x2 switching elements in nxn banyan network
A stage of n x n banyan network consists of (n/2) 2 x 2 switching elements. The first stage directs packets to the correct half of the network, the next stage to the correct quarter, and so on, until the packet is routed to the correct output.
Derive an expression for the number of 2 x 2 switching elements needed to make an n x n banyan network. Verify your answer for n = 8.