Match List I with List II
| List I | List II |
|---|---|
| A. Parallel FFT | I. Θ(n²) |
| B. Iterative FFT | II. Θ(n) |
| C. Evaluation of polynomial at n points by Horner method | III. Θ(lg n) |
| D. Product of two polynomials represented in point-value form | IV. Θ(n lg n) |
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
Parallel FFT runs in Θ(lg n) (III). Iterative FFT is Θ(n lg n) (IV). Evaluating a polynomial at n points by Horner's rule is Θ(n²) (I). Multiplying two polynomials in point-value form is Θ(n) (II).More Data Structures and Algorithms questions
- Let f(n) and g(n) be asymptotically positive functions. Statement I: f(n) ≥ 1 and f(n) = O(g(n)) ⇒ g(n) = Ω(f(n)). Statement II: f(n) = O(g…
- Consider the following statements: A. If some NP-complete problem is in P, then P = NP. B. TSP is in NP. C. SAT is in NP. D. The Hamiltonia…
- A B-tree used as an index for a large database table has four levels including the root node. If a new key is inserted into this index, the…
- Suppose a circular queue of capacity n − 1 elements is implemented with an array of n elements. Insertion and deletion use REAR and FRONT a…
- Given below are two statements: one is labelled as Assertion A and the other is labelled as Reason R. Assertion A: AVL trees are more balan…
- Consider a hash table of size 7 with starting index 0 and hash function (6x + 3) mod 4. Assuming the table is initially empty, which of the…