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

$\small \begin{array}{|c|l|l|l|l|} \hline
&\mathbf{(\log N)^{\frac{1}{2}}} \text{ find} & \mathbf{N} \text{ insert} &  \mathbf{(\log N)^{\frac{1}{2}}} \text{delete} & \mathbf{(\log N)^{\frac{1}{2}}}  \text{decrease-key} \\ \hline
\text{Unsorted Array} & O(N (\log N)^{\frac{1}{2}}) &O(N) &O(\log N)^{\frac{1}{2}})&O(\log N)^{\frac{1}{2}})\\ \text{Min-heap} &O(N (\log N)^{\frac{1}{2}})&O(N \log N)&O(\log N)^{\frac{3}{2}})&O((\log N)^{\frac{3}{2}})\\ \text{Sorted Array} &O((\log N)^{\frac{3}{2}})&O(N^2)&O(N (\log N)^{\frac{1}{2}})&O(N (\log N)^{\frac{1}{2}})\\ \text{Sorted doubly linked-list} &O(N (\log N)^{\frac{1}{2}})&O(N^2)&O((\log N)^{\frac{1}{2}})&O(N (\log N)^{\frac{1}{2}})\\\hline \end{array}$

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.

Correct Answer: $A$

Comments

For N insert operation MinHeap will take O(N) through build-heap method but for the decrease key MinHeap will take O(logN) for each element. And that is why A.

---

even if takes log n ,the total complexity will be logn^3/2 isnt it for min heap?..since there are logn^1/2 decrease key operations..

---

Yes. You are correct. Corrected now.

---

dont we need to shift the elements after deleting in case of unsorted array?....if we shift the elements after decrease key operation,then O(n) should be the complexity..please correct me if i am wrong.

---

You are correct for sorted array.

For unsorted array, we can simply swap the element to be deleted with the last element of the array and remove the last element- O(1).

---

ok i got it..and dont we need to sort the array again after decrease key operation in case of sorted array?

---

We needn't sort the array completely- just need to place the affected element in the new place and shift other elements by 1- same as in normal insertion sort.

---

@Arjun, we are counting O(log N)^1/2) for delete & decrease key for Unsorted array , because we are not considering cost of searching the key before deleting right ? I suppose that must be it, as if we consider cost of searching before deleting/decrease min in unsorted array then it'll take O(NlogN) !

---

yes, thats mentioned in question..

---

Yep, I missed reading that !

---

How are you writing all the complexities against find insert delete and decrease-key operations ?!
I only knew that searching an array takes O (n) time Heap Algorithm takes O(n log n )

Please explain me how to write the complexities
Help me understand the  concepts

---

Find operations for min-heap should be (logN)^3/2

---

Find in Min-Heap takes $O(N)$.

---

Sir, Can you explain a bit? or at least some good read..

---

You can consider the case where we are finding the max element in a Min-Heap. This could occur in any of the $n/2$ leaf nodes.

---

Okay. Thanks Sir.

---

halo sir,

may be a silly question, cannot understand fully.  though a pointer is provided, first locating the key that contains the pointer should be done right , to delete a key, so wouldnt delete for an unsorted array take O(N(logN)^1/2) ??

also i cannot understand

Sorted Array	O( (log N)3/2)	O(N2)	O(N (log N)1/2)

thanks in advance 

---

Please explain me how are we going to answer this question.A detailed explanation is needed please it's a request how are we getting these complexities while performing  (log N)1/2

---

Post a new quetion then u got cleared answer.

---

Why this decrease key in sorted array and in sorted  doubly linked is N(log N)^1/2. Why are we multiplying N with it since we have a pointer that tells what element is to be decreased then that will take O(1) Since it is already prepared what the element is to be decreased.Pointer will no longer be requiring scanning of the list as pointer will take us to that element in no time.

Please explain me where I am going wrong in understanding the question.

---

@Harsh Say for a sorted array- after decreasing the element we must ensure it is again sorted. So, we must find the new position. Same for sorted doubly linked list.

---

It is written that " 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".

Doesn't it mean that these two operations are $O(1)$.

---

No ..

Generally to delete or to do decrease key operation we need to first locate the element then perform respective operation(i.e. delete/ dec-key).

For that locate operation time is required say for unsorted array it is O(n) for sorted array O(logn)...but here they specified that we need O(1) for locate operation..

But we need to consider time for operations after locate operation means for delete and decrease key.

---

How can one build a table like this ?  Where can I read about operations like decrease - key ? Any good resource ?

---

Actually unsorted array decrease key has no meaning, as it is unsorted

Min heap has max size for an element to be sorted is log N , So, decrease key $\Theta ((log N)^{3/2})$

Similarly others too

---

cn ny simplify it more or tell it in simple terms ?

---

Sir, @Arjun Even if we follow this table both A & B has same overall complexity. Am I missing something?

---

I m geting following for

                   insert- N^2(logN)

                   decrease- o(1)(logN)N(logN)^1/2  please someone tell where i m wrong

                    for decrease- o(1) to decrease , O(logn) to find position where new decrease value to be                              inserted, It might require O(n) swap , and so for (logN)^1/2 element it will be  o(1)                                       O(n(logn)^3/2)

 

 

 

 

//

---

@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 -> -

Please explain?

---

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 n^1/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 N^1/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

---

@Arjun Sir,

Deletion in unsorted array will take O(n) time, as srestha mentioned that if element is deleted from middle then we need to do n swaps to fill the gap. Please clarify?

---

@arjun sir

as we are not deleting min from min heap..we are deleting a node which is pointed by pointer..it can be internal node also..so how the complexity of deleting internal node in min heap is logn????

---

Can anyone explain why $(log n)^\frac{1}{2}$ decrease key operations of sorted array and sorted doubly linked list is $O(n(log n)^\frac{1}{2})$?

---

After performing the decrease key operation in a sorted array you need to perform upto n shift operation to make array again sorted. Same for sorted doubly linked list . 

So (logn)^1/2 Each take n time i.e. O(n(logn)^1/2)

 

 

---

@Arjun sir,

Cost of deletion in unsorted array should be $O(n)$ for single operation and for such $\sqrt{logn}$ operation it should be $n\sqrt{logn}$

---

@Shubhanshu

"For a delete operation, a pointer is provided to the record that must be deleted".

This is given in the question. So no need to search for the element.

---

@Arjun sir,

 

@Anybody

The purpose of maintaining the min heap is to get the minimum element in O(1) time. So why have you not considered the fact that we are finding the minimum element in the min heap every time and finding root logn elements would be root logn time but not  n root logn.

---

Time complexity of deleting an element from unsorted array would be N*N

It's because pointer to element that has to decreased or deleted is only given which mean index of that element is only given.

So swapping the element (that has to be deleted) with last element can't be performed. It's because we don't know the last index of the array.

So better to delete the element as we know only it's index and then shift the element one by one.

 

So, complexity come out to be O(n)
As n insert operations.

Therefore,

O(n*n)

@Arjun

---

@Ekta07_GATE 

This is how it will happen.

A[ 0 1 2 3 4 5 6....]  We want to delete the 5th element.

we don't know the last index but we know the first index so we can swap with the first one and reduce the size like this.

A[1 2 3 4 5 6....] 

If you observe here we have deleted the element so It so happen that we can be asked to delete the element at index 5 again and we will do this (logn)^1/2. 

 

Now what if we are asked to delete 0th index element after we have already deleted 18000 elements??

Our array is A[18000 18001 18002 18003...] so we will just have variable that knows the starting index of our array. Say mFirstIndexNumber = 18000 and mDeleteIndexNumber = 0

we'll do like this. 

swap(mFirstIndexNumber and mDeleteIndexNumber);

mFirstIndexNumber += 1;

This will take constant time to delete one element so we have to do like this (logn)^1/2 

so O(1)*(logn)^1/2 = O(logn)^1/2.

 

 

---

so for MIN-HEAP DELETION, we are just considering the cases wherein we need to just delete the minimum element and NOT the one pointed out by the pointer??

Because in that case, we’ll have to delete elements from min-heap and store it somewhere until we get the element pointed out by the pointer and then delete it and then insert back those elements which we initially deleted.

Am i right??

---

@Arjun sir, kindly explain why can't we use build heap method to do insertion in min heap here?

---

@Hira Thakur sir In sorted array to delete any desired no which is presnt in list we simply firstly search this element in arr in logn time then delete in O(n) time then total complexity should be taken as logn

but arjun sir taken in O(n ) why ?

Answer 2

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.

Comments

@Rajesh Pradhan

Great observation sir.

Thanks alot !

---

@Rajesh Pradhan
Amazing...
outstanding observation!

---

great observation!👍 btw its the actual concept 

Answer 3

This might help n(logn)^1/2

Comments

@Satbir

In case of  delete operation in doubly linked list .when we are given a pointer to the node to be deleted then we always consider swapping to be the default procedure .right?(which gives O(1) )

 

---

yes.

---

Why delete and decrease key operations for unsorted array is taking $O(n)$ time. Pointers are already provided for the items to be deleted or decreased. It should take $O(1)$. Therefore $\sqrt{logn}$ for both of them.

Answer 4

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.

Comments

nt a correct explanation ...

---

Please explain the delete and decrease key operations of min heap