Match List I with List II. List I: A. Parallel FFT, B. Iterative FFT, C. Evaluation of a polynomial at n points by Horner's method, D. Product of two polynomials represented in point-value form. List II: I. Θ(n²), II. Θ(n), III. Θ(lg n), IV. Θ(n lg n).

1. AA-III B-I C-II D-III
2. BA-II B-I C-III D-IV
3. CA-III B-IV C-I D-II
4. DA-II B-III C-IV D-I

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: C. A-III B-IV C-I D-II

Explanation

A parallel FFT circuit has depth Θ(lg n); the iterative FFT takes Θ(n lg n); Horner takes Θ(n) per point, so Θ(n²) for n points; multiplying in point-value form is pointwise, Θ(n).