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?

Let $k = (\log N)^{1/2}$. Note that $k \ll N$.

Let us evaluate the total asymptotic time complexity for each candidate data structure:

1. Unsorted array:

   • Insert: Insert at the end takes $O(1)$ time $\implies N \times O(1) = O(N)$.

   • Delete (with given pointer): Swap with the last element and decrement size in $O(1)$ time $\implies k \times O(1) = O(k)$.

   • Decrease-key (with given pointer): Update key in-place in $O(1)$ time $\implies k \times O(1) = O(k)$.

   • Find: Linear scan of array takes $O(N)$ time $\implies k \times O(N) = O(N(\log N)^{1/2})$.

   • Total time: $O(N + k + k + N(\log N)^{1/2}) = O(N(\log N)^{1/2})$.

2. Min-heap:

   • Insert: $O(\log N) \implies N \log N$.

   • Delete / Decrease-key: $O(\log N) \implies k \log N$.

   • Find: $O(N) \implies k N$.

   • Total time: $O(N \log N)$. Since $N \log N > N(\log N)^{1/2}$, this is asymptotically slower.

3. Sorted array / Sorted doubly linked list:

   • Insert: Takes $O(N)$ time per insertion $\implies N \times O(N) = O(N^2)$, which is much worse.

Therefore, the Unsorted array gives the minimum total asymptotic time complexity [p. 21, Q. 60].