The solution of recurrence relation : T(n) = 2T(sqrt(n)) + lg(n) is
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. O(lg(n) lg(lg(n)))
Explanation
Let n = 2ᵐ and S(m) = T(2ᵐ): S(m) = 2S(m/2) + m, so S(m) = O(m lg m). With m = lg n, T(n) = O(lg n · lg lg n).
More Data Structures and Algorithms questions
- The elements 42,25,30,40,22,35,26 are inserted one by one in the given order into a max-heap. The resultant max-heap is stored in an array…
- Consider two sequences X = ⟨0, 1, 2, 1, 3, 0, 1⟩ and Y = ⟨1, 3, 2, 0, 1, 0⟩. The length of the longest common subsequence of X and Y is
- Consider the postfix expression with single-digit operands: 6 2 3 * / 4 2 * + 6 8 * −. The top two elements of the stack after the second *…
- A binary search tree is constructed by inserting the following numbers in order : 60,25,72,15,30,68,101,13,18,47,70,34 The number of nodes…
- In a ternary tree, the number of internal nodes of degree 1,2 , and 3 is 4,3 , and 3 respectively. The number of leaf nodes in the ternary…
- Match List I with List II and choose the correct answer from the code given below. Where V and E are the number of vertices and edges in th…