The tight asymptotic bound for the recurrence T(n) = 2T(n/4) + √n is
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: C. Θ(√n log n)
Explanation
a = 2, b = 4, so nlog₄2 = n1/2 = √n, which equals f(n). By case 2 of the Master theorem, T(n) = Θ(√n log n).More Data Structures and Algorithms questions
- When developing a dynamic programming algorithm, the sequence of steps followed is: A. Construct an optimal solution from computed informat…
- The correct sequence of constructing a Huffman tree is A. Repeat until root formed B. Create leaf nodes C. Build priority queue D. Combine…
- Choose the correct statement(s) A. A problem which is NP-Complete will have the property that it can be solved in polynomial time iff all o…
- Consider the binary tree: A is the root with left child B and right child C; C has left child D and right child E; E has right child F; F h…
- Which of the following uses only increment operations for adding and removing elements at either end?
- Match List I with List IIList I List II A. Breadth First Search I. LISP B. Depth First Search II. Syntax tree C. Prefix III. Stack D. Infix…