The time complexity to multiply two polynomials of degree n using Fast Fourier transform method is :
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. θ(n lg n)
Explanation
FFT evaluation, pointwise multiplication and inverse FFT take Θ(n lg n).
More Data Structures and Algorithms questions
- The following multithreaded algorithm computes transpose of a matrix in parallel : p Trans (X, Y, N) if N = 1 ← then Y[1,1] X[1,1] else par…
- Consider the following statements : (a) The running time of dynamic programming θ(ρ) ρ algorithm is alway where is number of subproblems. (…
- With preconditions p ≥ 1 and n ≥ 0 (no overflow): int x = p; int k = n; int m = 1; while (k != 0) { if (k is odd) m = m * x; x = x * x; k =…
- Match List I with List II. List I: (a) Prim's algorithm, (b) Dijkstra's algorithm, (c) Faster all-pairs shortest path, (d) Edmonds-Karp alg…
- There are many sorting algorithms based on comparison. The running time of heapsort O(n lg n) P Q algorithm is . Like , but unlike , (P, Q)…
- Which of the following is best running time to n n2 − 1 sort integers in the range 0 to ?