2.7k 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
retagged | 2.7k views

(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.

selected by
@Arjun Sir

@Bikram,

@srestha, I am not getting how you get this table. what is the no of elements you are considering in the data structure

If you are considering data structure contain n elements then (As per answer is Unsorted array):-

insert -> O(1);

delete -> O(n);

find -> O(n);

delete key -> -

insert is O(1), but there is N element, i.e why it will take O(N)

For delete here one pointer is provided , i.e. why delete taking O(1) time
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

Still  problem lies

In unsorted array deletion

it has a pointer provided

So, O(1) time to delete operation. Now, there are log n1/2 operations

But if it delete from middle say i, then we need to swap back all element 1 position after ith element to fill the gap.

So, here n more operation required.

So, total complexity will be O(N log N1/2)

chk it

Deletion is linked list is nothing deleing node and modify pointer(address field) so why You do swapping.

You are assuming array.
ohh, printing mistake was there :P
it will be for unsorted array

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.

edited

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!

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.
+1 vote

This might help n(logn)^1/2