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(n) = 3T(n/3) + n
(D) T(n) = 2T(n/2) + √n
(E) T(n) = T(n−1) + 1
Choose the correct answer from the options given below:
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. (A), (E), (D), (B), (C)
Explanation
(A) Θ(log n); (E) Θ(n); (D) Θ(n) by Master theorem case 1; (B) and (C) Θ(n log n). Increasing order: A, E, D, B, C.More Data Structures and Algorithms questions
- 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…
- Arrange the following steps in the correct order to solve the Knapsack problem using Dynamic Programming. (A) Define the base case when the…
- Match List I (Recurrence Relation) with List II (Complexity)List I List II (A) T(n) = 2T(n/2) + n (I) T(n) = Θ(n log n) {exact solution} (B…
- Which of the following is NOT a palindromic subsequence of the string "ababcdabba"?