The GATE Grind

GATE 2015 CS – Question 60

Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple choice

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?

  1. Unsorted array
  2. Min-heap
  3. Sorted array
  4. Sorted doubly linked list

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) Unsorted array

Explanation

With an unsorted array, an insert is $O(1)$, and a delete or decrease-key with a pointer is $O(1)$. A find costs $O(N)$, and there are only $(\log N)^{1/2}$ of them, so the total is $O(N + N\sqrt{\log N}) = O(N\sqrt{\log N})$. A min-heap pays $O(\log N)$ for each of the $N$ inserts, giving $O(N \log N)$, which is larger. A sorted array and a sorted list pay $O(N)$ per insert, giving $O(N^2)$.