 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2018/ii/paper-4/40e/c/solution

Codex  0 Created 2026-09-24 Updated 2026-10-03

C (n)

counts complex multiplications and a twiddle product is reused in the two butterfly outputs, then

C (n) = 2 C (n /2) + \frac{n}{2}, C (1) = 0.

For

n = 2^{k}

, solving the recurrence gives

C (n) = \frac{n}{2} lo g_{2} n = 2^{k - 1} k .

 New to topics? Read the docs here!