Match List - I with List - II.
| List - I | List - II |
|---|---|
| A. Merge sort | I. n² |
| B. Binary search | II. nlogn |
| C. Quick sort | III. n |
| D. Search in an unsorted array | IV. logn |
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. A-II, B-IV, C-I, D-III
Explanation
Merge sort has O(n log n) time complexity in all cases, giving A-II. Binary search on a sorted array takes O(log n) comparisons, giving B-IV. Quick sort's worst-case time complexity (e.g. an already sorted input with a poor pivot choice) is O(n²), giving C-I. A sequential search through an unsorted array requires O(n) comparisons in the worst case, giving D-III. So the correct match is A-II, B-IV, C-I, D-III.More Data Structures and Algorithms questions
- Consider the following AVL tree: root = 60; left child of 60 = 50; right child of 60 = 70; right child of 70 = 80 (a balanced AVL tree of h…
- In the worst case, the smallest number of comparisons required by any sorting algorithm, which does only binary comparisons, is
- A problem of size n requires n² bit operations. What is the largest size instance that can be solved in 1 second, if each bit operation is…
- If f(n) = θ(g(n)) and g(n) = O(h(n)), then which of the following is true?
- The number of leaf nodes in a full 4-ary rooted tree of n nodes is
- Which of the following statements maybe false for a decision problem X ∈ NP?