Project ForgeAn 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?
- Unsorted array
- BMin-heap
- CSorted array
- DSorted doubly linked list
Explanation
With an unsorted array: N inserts cost O(1) each (append) = O(N) total; delete-with-pointer and decrease-key-with-pointer are both O(1) each since no ordering needs to be maintained; only 'find' (which has no pointer) needs an O(N) linear scan, done (log N)^(1/2) times = O(N·(log N)^(1/2)) — the dominant term overall. With a min-heap: inserts cost O(log N) each = O(N log N) total, which already exceeds O(N·(log N)^(1/2)) since log N grows faster than (log N)^(1/2) — so the heap is asymptotically worse despite its faster decrease-key/delete. Sorted structures make the N inserts even more expensive (O(N) or O(N²) total). The unsorted array's O(N·(log N)^(1/2)) total beats every alternative.
Source: GATE CS 2015 (Session 1 / 7th Feb Shift 1) (2015)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.