GATE CSE
First time here? Checkout the FAQ!
x
+18 votes
2.4k views

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
asked in Algorithms by Veteran (38.7k points)  
retagged by | 2.4k views

4 Answers

+34 votes
Best answer
  (log N)1/2 find N insert  (log N)1/2 delete (log N)1/2 decrease-key
Unsorted Array O(N (log N)1/2) O(N) O(log N)1/2) O(log N)1/2)
Min-heap O( N (log N)1/2) O(N log N) O( (log N)3/2) O( (log N)3/2)
Sorted Array O( (log N)3/2) O(N2) O(N (log N)1/2) O(N (log N)1/2)
Sorted doubly linked-list O(N (log N)1/2) O(N2) O( (log N)1/2) O( N(log N)1/2)


So, Unsorted array is the answer.

The operations given can be performed in any order. So, for Min-heap we cannot do the usual BuildHeap method. 

Delete in unsorted array is O(1) as we can just swap the deleted element with the last element in the array and delete the last element. 

For sorted-doubly linked-list we cannot do binary search as this would require another array to maintain the pointers to the nodes. 

answered by Veteran (294k points)  
selected by
Some confusion in this question

Min heap decrease key , time complexity should be $N\left ( log N \right )^{\frac{5}{2}}$

Sorted array delete should be $\left ( log n \right )^{\frac{1}{2}}$

because we already know delete and insert time of every element and decrease key operation is nothing but delete and then insert operation

So, if we multiply delete and insert operation we get decrease key, rt?

@srestha

 

Min heap decrease key , time complexity should be N (log N)3/2

No, it is not.

the decrease key operation in  MinHeap will take O(logN) for each element so in total it is (log N)3/2

as in question it says , " (log N)1/2 decrease-key operations on a set of data items with keys drawn from a linearly ordered set " so log N * (log N) 1/2 = (log N)1+1/2  =  (log N)3/2 

 

@srestha

 

Sorted array delete should be (logn)1/2

No, it is not the way .

Delete in sorted array done in O(n) for each element , now in question says " algorithm takes  (log N)1/2 delete operations, "

so O(n) * (log N)1/2 = N (log N)1/2 

Hence Sorted array delete is N (log N)1/2 

Why O( (log N)1/2)  for deletion in sorted linked list?? Because sorted linked list will take O(1) time to delete only if pointer is provided to the previous element where we want to delete??

I know it wont change the answer but still ....?

An algorithm performs (log N)1/2 find operations , N insert operations, (log N)1/2 delete operations, 

means  total number of delete operations are (log N)1/2

now sorted linked list will take O(1) time to delete

 total time = O(1) * (log N)1/2

= O (log N)1/2

+6 votes

I got the same table as Arjun sir got.

& Everybody must know that how it derived.

But I think for average mind like me it will time-consuming in exam.

I have one observation while I read this question.

Imp Note : I have Considered (find,insert,delete,dec-key) operations while giving ans.

Before and After doing operations on data structure x it is required that it should be data structure x only.Now replace x with given data structures.

So If it is a heap then after doing specified operations(find,insert,delete,dec-key) it should be heap only.

Means Heap Constraint need to be satisfied. Same phenomena applicable for other data structure.

So max time is consuming in fulfilling that constraint.

That's why Unsorted Array (where no such constraint) won the Race compare to Heap,Sorted array and Sorted doubly linked list which are truely structured.

So Option A. unsorted array is Ans.

PS:- 1. Plz verify my ans. And comment if u r not agree.

2. Must realize Arjun sir's Ans.

answered by Veteran (18.6k points)  
edited by

Sorted Array  in N insert  O(N2), because to make room for 1 element worst case takes O(N) time and for N elements takes O(N2) time, rt?

Correct.
We're same minded people bro!
+2 votes
Answer : A

The time complexity of insert in unsorted array is O(1), O(Logn) in Min-Heap, O(n) in sorted array and sorted DLL.

Since number of insertion operations is asymptotically higher, unsorted array is preferred.
answered by Loyal (4.2k points)  
+1 vote
answer is a
answered by Active (1.4k points)  
Answer:

Related questions



Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2076 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,038 questions
33,649 answers
79,695 comments
31,069 users