GATE CS 2015 Set 1 Q40 — Asymptotic Worst Case Time and Space Complexity

To find the most suitable data structure, we analyze the total asymptotic cost for each option based on the given operation counts:

• Find: $(\log N)^{1/2}$ operations
• Insert: $N$ operations
• Delete (pointer given): $(\log N)^{1/2}$ operations
• Decrease-key (pointer given): $(\log N)^{1/2}$ operations

Let us evaluate the total cost for each data structure:

1. Unsorted Array:
   • Insert: $O(1)$ per operation $\implies$ Total $O(N)$
   • Find: $O(N)$ per operation $\implies$ Total $O(N (\log N)^{1/2})$
   • Delete: $O(1)$ (swap with the last element) $\implies$ Total $O((\log N)^{1/2})$
   • Decrease-key: $O(1)$ (no order to maintain) $\implies$ Total $O((\log N)^{1/2})$
   • Total Cost: $O(N (\log N)^{1/2})$
2. Min-heap:
   • Insert: $O(\log N)$ per operation $\implies$ Total $O(N \log N)$
   • Find: $O(N)$ per operation (linear search) $\implies$ Total $O(N (\log N)^{1/2})$
   • Total Cost: $O(N \log N)$ (since $N \log N > N (\log N)^{1/2}$)
3. Sorted Array:
   • Insert: $O(N)$ per operation (due to shifting) $\implies$ Total $O(N^2)$
   • Total Cost: $O(N^2)$
4. Sorted Doubly Linked List:
   • Insert: $O(N)$ per operation (to find position) $\implies$ Total $O(N^2)$
   • Total Cost: $O(N^2)$

Comparing the total complexities, the Unsorted Array achieves the lowest overall asymptotic complexity of $O(N (\log N)^{1/2})$.