A stage of an $n \times n$ banyan network consists of $(n/2) 2 \times 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 \times 2$ switching elements needed to make an $n \times n$ banyan network. Verify your answer for $n = 8$.
