Which of the following is the solution of the recurrence relation T(n) = T(2n/3) + 1?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. Θ(log n)
Explanation
a = 1, b = 3/2, so nlog_b a = n⁰ = 1 = f(n). By Master theorem case 2, T(n) = Θ(log n).More Data Structures and Algorithms questions
- Which of the following description(s) is/are true? A. Red-Black Tree – guarantees worst case O(log n) time for search, insert & delete. B.…
- Match List I with List IIList I List II A. Insertion Sort I. O(log n) B. Binary Search II. O(n²) C. Quick Sort III. O(n) D. Selection Sort…
- Arrange the following recurrence relations in increasing order of their time complexity: (A) T(n) = T(n/2) + 1 (B) T(n) = 2T(n/2) + n (C) T…
- Select the sorting algorithms that are stable. (A) Quick Sort (B) Bubble Sort (C) Insertion Sort (D) Merge Sort (E) Shell Sort Choose the c…
- ______ is a self-balancing binary search tree where the path from the root to the farthest leaf is no more than twice as long as the path f…
- Match List I with List IIList I List II (A) Dijkstra's Algorithm (I) Finds the shortest path between all pairs of vertices in a graph with…