Solution

The correct answer is A - III, B - IV, C - I, D - II

Key Points

• A - Parallel Fast Fourier Transform (FFT):
  • The FFT can be executed in parallel, which reduces the time complexity from O(n log n) to O(log n) under ideal conditions, as the operations required to calculate the FFT can be effectively divided among multiple processors. Thus, it corresponds to III. Θ (lg n).
• B - Iterative Fast Fourier Transform (FFT):
  • The FFT, even when implemented iteratively, has a time complexity of O(n log n) because we divide the problem into smaller chunks recursively, and for each level of division, we do a constant amount of work. Hence it matches with IV. Θ (n lg n).
• C - Evaluation of polynomial at n points by Horner method:
  • If evaluated using the Horner method, a polynomial can be evaluated in O(n) operations. However, if we're evaluating the polynomial at n points, and the polynomial itself has degree n, the total complexity becomes O(n^2). Therefore, it corresponds to I. Θ (n^2).
• D - Product of two polynomials that are represented in point value form:
  • If the polynomials are represented in point-value form, their product can be computed pretty efficiently in O(n) time complexity. This is due to the fact that to compute the product polynomial at a point, you simply multiply the evaluations of the input polynomials at that point. However, a complete Fast Fourier Transform involves conversion back from point-value representation to coefficient representation, which takes O(n log n). As the question doesn't ask for this final conversion back, we'll go with II. Θ (n).

That's why the correct answer is option 3.