An algorithm performs \((\log N)^{1/2}\) find operations, \(N\) insert…
2015
An algorithm performs \((\log N)^{1/2}\) find operations, \(N\) insert operations, \((\log N)^{1/2}\) delete operations, and \((\log N)^{1/2}\) decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?
- A.
Unsorted array
- B.
Min-heap
- C.
Sorted array
- D.
Sorted doubly linked list
Attempted by 87 students.
Show answer & explanation
Correct answer: A
Key idea: compute the total cost contribution of each operation for each data structure and compare the dominating terms.
Unsorted array: find (search by key) is O(N) each ⇒ (log N)^{1/2} · N = N·(log N)^{1/2}; insert is O(1) each ⇒ N; delete (pointer) and decrease-key (pointer) are O(1) each ⇒ lower-order. Total dominated by N·(log N)^{1/2}.
Min-heap: find (search by key) is O(N) each ⇒ N·(log N)^{1/2}; insert is O(log N) each ⇒ N log N; delete (pointer) and decrease-key are O(log N) each ⇒ (log N)^{3/2} total. Total dominated by N log N.
Sorted array or sorted doubly linked list: inserting in sorted order costs O(N) each ⇒ N^2 total, which is far worse than the other choices.
Conclusion: Since N·(log N)^{1/2} (unsorted array) is asymptotically smaller than N log N (min-heap) and N^2 (sorted structures), the unsorted array gives the best total asymptotic complexity for the given operation mix.