7.7k views

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?

1. Unsorted array
2. Min - heap
3. Sorted array

edited | 7.7k views
+1
"with keys from a linearly ordered set"  what is this line means?
0

@Arjun , Can you please explain how you are saying insertion and deletion in an unsorted array takes only O(1) time? . Arrays are a static data structures unlike heap and linked list. Adding/removing a single element in an array requires complete deletion of the current array and creation of another new array which is definitely not an O(1) operation and should be O(n). Please correct me if I am wrong.

$\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.

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$
by Veteran (431k points)
edited
0
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)

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

0
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
0
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?
0

@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

+1

@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

+1

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

+1

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

0

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

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

You are assuming array.
0
ohh, printing mistake was there :P
it will be for unsorted array
0
@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?
0
@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????
0
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})$?
+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)

+1
@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}$
0

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

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

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

0

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.

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.

by Boss (23.9k points)
edited
+2

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?

+1
Correct.
+4
We're same minded people bro!
0

Great observation sir.

Thanks alot !

This might help n(logn)^1/2

by Active (2.1k points)
0
@Arjun Sir How the complexity of delete operation in min heap is log n ? Please explain.
0

In the worst case suppose we delete the root. then copy one of the leaf node to the root and call heapify() on the root as the left subtree is min heap as well as right subtree. heapify() will take logn time.

0
what is the complexity if we delete a internal node from min heap in worst case?????
0
since we have been provided a pointer at which we have to do delete operation .

so we go to that element and delete it

and replace it with leaf node

and apply heapify on that subtree(where deleted element position is root)

hence O(log n) time.
0

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

0
yes.

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.
by Active (2.8k points)
+1
nt a correct explanation ...
0
Please explain the delete and decrease key operations of min heap