Give tight bounds for T(n) = 4T(√n) + lg²n, with T(n) constant for n ≤ 2.
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. Θ(lg² n lg lg n)
Explanation
Let m = lg n, S(m) = T(2ᵐ): S(m) = 4S(m/2) + m². Master theorem case 2 gives Θ(m² lg m) = Θ(lg²n lg lg n).
More Data Structures and Algorithms questions
- Consider a weighted directed graph. The current shortest distance from source S to node x is represented by d[x]. Let d[v]= 29, d[u]= 15, w…
- When using Dijkstra's algorithm to find shortest path in a graph, which of the following statement is not true?
- The time complexity to multiply two polynomials of degree n using Fast Fourier transform method is :
- 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 =…