An algorithm performs (log N)1/2 find operations, N insert operations, (log…
2024
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 2 students.
Show answer & explanation
Correct answer: A
Concept
When an algorithm performs several different operations a different number of times, a candidate data structure's total asymptotic cost is the sum of (cost of one instance of an operation × how many times it is performed) over every operation type. Compare that total across candidates and pick the one whose dominant, fastest-growing term is smallest. Here N insert operations vastly outnumber the (log N)^(1/2) find, delete, and decrease-key operations, so the per-insertion cost usually decides the winner.
Application
For each candidate below, the cost of one instance of an operation is multiplied by how many times that operation runs, then all four contributions are summed to find the dominant term.
Data structure | Insert (× N) | Find (× √(log N)) | Delete by pointer (× √(log N)) | Decrease-key by pointer (× √(log N)) | Dominant total |
|---|---|---|---|---|---|
Unsorted array | O(1) → O(N) | O(N) → O(N·√(log N)) | O(1) → O(√(log N)) | O(1) → O(√(log N)) | O(N·√(log N)) |
Min-heap | O(log N) → O(N log N) | O(N) → O(N·√(log N)) | O(log N) → O(√(log N)·log N) | O(log N) → O(√(log N)·log N) | O(N log N) |
Sorted array | O(N) → O(N2) | O(log N) → O(√(log N)·log N) | O(N) → O(N·√(log N)) | O(N) → O(N·√(log N)) | O(N2) |
Sorted doubly linked list | O(N) → O(N2) | O(N) → O(N·√(log N)) | O(1) → O(√(log N)) | O(N) → O(N·√(log N)) | O(N2) |
Cross-check
For large N, √(log N) < log N ≪ N, so the four dominant totals order as O(N·√(log N)) < O(N log N) < O(N²). The unsorted array's total is asymptotically the smallest of the four, so it is the most suited structure for this exact operation mix. The min-heap is the next best, but its O(N log N) insertion cost is strictly worse; both sorted structures pay an O(N²) insertion penalty that dominates regardless of how cheap their delete or decrease-key operations are once a pointer is already given.