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) T(n) = T(n/2) + 1 | (II) O(n²) |
| (C) T(n) = 2T(n/2) + 1 | (III) T(n) = Θ(n) {exact solution} |
| (D) T(n) = T(n−1) + n | (IV) O(n) |
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. (A)-(I), (B)-(IV), (C)-(III), (D)-(II)
Explanation
2T(n/2) + n = Θ(n log n) exactly (A-I). T(n/2) + 1 = Θ(log n), which is O(n) but not Θ(n) (B-IV). 2T(n/2) + 1 = Θ(n) exactly (C-III). T(n−1) + n = Θ(n²) (D-II). Note: some published keys print option C, which pairs T(n/2) + 1 with 'Θ(n) exact', and that is mathematically incorrect.More Data Structures and Algorithms questions
- Which of the following is NOT a palindromic subsequence of the string "ababcdabba"?
- Which of the following is TRUE?
- What is the result of evaluating the postfix expression "4 3 * 2 5 * + 8 -"?
- Which data structure is typically used to implement a hash table?
- Which collision resolution technique involves maintaining a linked list of collided keys?
- Consider the following functions: f(n) = 3n√n, g(n) = 2√n log₂ n, h(n) = n!. Which of the following is true?