Question 50

Given operation counts with $k = (\log N)^{1/2}$:

• Find: $k = (\log N)^{1/2}$ operations
• Insert: $N$ operations
• Delete: $k = (\log N)^{1/2}$ operations (record pointer provided)
• Decrease-Key: $k = (\log N)^{1/2}$ operations (record pointer provided)

Analyzing each data structure:

1. Unsorted Array:

   • Insert: $O(1) \implies N \times O(1) = O(N)$.
   • Find: $O(N) \implies (\log N)^{1/2} \times O(N) = O(N (\log N)^{1/2})$.
   • Delete (with pointer): $O(1)$ by swapping target element with last element $\implies O((\log N)^{1/2})$.
   • Decrease-Key (with pointer): $O(1)$ direct update $\implies O((\log N)^{1/2})$.
   $$\text{Total Cost} = O(N (\log N)^{1/2}).$$

2. Min-Heap:

   • Insert: $O(\log N) \implies N \times O(\log N) = O(N \log N)$.
     Since $N \log N > N (\log N)^{1/2}$, Min-Heap is asymptotically slower.

3. Sorted Array / Sorted Doubly Linked List:

   • Insert takes $O(N)$ time, leading to $N \times O(N) = O(N^2)$ total cost, which is strictly worse.

Therefore, the unsorted array achieves the best total asymptotic complexity of $O(N (\log N)^{1/2})$ (option A).