GATE CSE 2015 Set 1 | Question: 40

Question

An algorithm performs $(\log N)^{\frac{1}{2}}$ find operations , $N$ insert operations, $(\log N)^{\frac{1}{2}}$ delete operations, and $(\log N)^{\frac{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?

• A. Unsorted array
• B. Min - heap
• C. Sorted array
• D. Sorted doubly linked list

Comments

can someone explain why

with keys from a linearly ordered set

statement is given in the question? 

---

https://www.youtube.com/watch?v=w_hXSoP2DyE

---

Any one please explain what is the meaning of decrease key operation ?

Answer 1

For Unsorted Array

Find takes O(N) time as we have to scan all the elements so for $O(logN)$$^1$$^/$$^2$ find operations =O(N$(logN)$$^1$$^/$$^2$)

Insertion takes O(1) time as we will insert at the end of array so for O(N) insertions = $O(1)*O(N)=O(N)$

For Deletion a pointer is given so we will swap pointed element with last element and delete it which takes O(!) time, so for $O(logN)$$^1$$^/$$^2$ deletions = O(1)*$O(logN)$$^1$$^/$$^2$=$O(logN)$$^1$$^/$$^2$.

for Decrease Key a pointer is given so we can decrease key in O(1) time so for $O(logN)$$^1$$^/$$^2$ decrease key operations = O(1)*$O(logN)$$^1$$^/$$^2$=$O(logN)$$^1$$^/$$^2$.

in the same way analyse other data structures 

and then check table given by Arjun sir.

 Unsorted array is the answer