GATE CSE 2016 Set 2 | Question: 15

Question

$N$ items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided to the record to be deleted. For a decrease-key operation, a pointer is provided to the record on which the operation is to be performed.

An algorithm performs the following operations on the list in this order: $\Theta \left(N\right)$ delete, $O (\log N)$ insert, $O(\log N)$ find, and $\Theta(N)$ decrease-key. What is the time complexity of all these operations put together?

• A. $O(\log^{2} N)$
• B. $O(N)$
• C. $O(N^{2})$
• D. $\Theta\left(N^{2}\log N\right)$

Comments

only 1 delete , 1 insert , 1 decrease key operations are performed?

---

can't understand.please give clear explanation

---

How many delete operations are performed in all? Its not very clear from the question.

---

The time complexity of decrease-key operation is Θ(1) since we have the pointer to the record where we have to perform the operation. However, we must keep the doubly linked list sorted and after the decrease-key operation we need to find the new location of the key. This step will take Θ(N) time and since there are Θ(N) decrease-key operations, the time complexity becomes O(N²).

https://www.geeksforgeeks.org/gate-gate-cs-2016-set-2-question-25/

---

That's the problem right, we need to assume that sorted implicitly means it will have to remain sorted. I don't understand why can't they just clearly mention. But I guess that's there point to see how carefully you read the question.

---

At the end we have logn elements therefore for decreasing in this wil take O(1) and for keeping the doubly liNk list sorted it will take O(long) times. Hence total time taken nlogn. Correct Option is not given.

---

See it once 

---

Sir I know this. Not a satisfactory answer.

---

please tell about decrease key

---

@Usman list is sorted means after decrease key the property has to be maintained ..means yes we will have pointer to a node for decrease key operation but after that we have to search its right position in the list for that we have to search the entire list in worst case which is O(n) so overall for one decrease key operation it will take O(n) and for n decrease key O($n^{2}$)

---

The key to this question is knowing that reaching to an element in a sorted Linked List would take $O(n)$ time and not $O(logn)$

One might think that similar to the case in sorted arrays, we can apply binary search on Linked Lists and get $O(logn)$ complexity, but that's incorrect.

Arrays provide direct access. We can directly go to the $i$th element.

Linked Lists only provide linear access. So, even if you apply binary search on Linked Lists, you'd still need to traverse each and every node in the worst case, hence this takes $O(n)$ time.

---

So, for decrease key; it'll be $O(N*1*N)=O(N^2)$ time.

---

I understood how delete is $O(N)$, but we are doing $N$ delete operations, so it must be $O(N^2)$, right?

---

No, for one delete operation in given doubly linked list we would just need $O(1)$ time, since we directly have the pointer to the node to be deleted, and then we perform $O(N)$ delete operations i.e $O(N) * O(1) = O(N)$ for delete operation effectively.

---

So we don't have to keep the array in the sorted order after deletion?

---

Since the given linked list is already sorted, Delete operation would never disturb it’s sort order. The sort order would only be affected by the Decrease Key operation.

---

@Sachin Mittal 1 sir , whats the role of this line from An algorithm ….. till decrease key ??  as insertion and find operations takes O(n) time but how they have given logn time ?? is this line for 'n' elements if not then how for deletion it takes O(n) time? because after deletion of element the list already remains in sorted order . 

---

Initial size of LL is given as N(in 1^st para)

The line in 2^nd para “An algorithm performs the following operations on the list in this order: θ(N) delete means at first we are deleting either N or N/2 or N/3 or N/4...(must be in θ(N) set) from a LL of N elements. Then we are performing O(logN) insertions means no of insertions are <=logN. Similarly O(logN) find means we are calling find() function <=logN times. θ(N) decrease key means we are calling decrease key function either N or N/2..(must be in θ(N) set) times. Don’t confuse it with time complexity, these are not the time complexities. 

You can create two cases. In case 1 consider that no of elements that are deleted <N i.e either N/2 elements are deleted or N/3 or N/4 or N/5...(must be in θ(N) set). Here the length of remaining LL will be in O(N) (ie either N/2 or 2N/3 or..) after delete operation.

In case 2 consider that all N elements are deleted.Here the length of remaining LL will be 0 after delete operation. After insert() length of LL will be <= logN.

Time complexities of each operation are different in both the cases because the length of the LL is different.

Case 1 time complexities: address of element to be deleted is given so delete() will take O(1) time. Insert() and find() will take O(N) time as length of LL is in O(N) .In dec key() first we have to delete that element whose address is given then insert that new decremented value. So delete will take const time but insertion would take O(N) time . So time complexity of dec key() will be O(N) . We are calling dec key() θ(N) times so time complexity will be O(N^2).

Rest of the thing you can understand from best answer :)

---

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

Answer 1

Answer is (C).

• Delete $O(1)$
• Insert $O(N)$
• Find $O(N)$

Decrease Key $\Rightarrow O(N)$ //Because we need to search position in Linked list. (It is similar to a Delete followed by an Insert with the decreased value)

• $O(n)$ delete $\Rightarrow O(N \times 1 ) =O(N)$
• $O(\log N)$ find $\Rightarrow O(\log N \times N ) = O(N \log N)$
• $O(\log N)$ insert $\Rightarrow O(N \log N)$
• $O(N)$ decrease key $\Rightarrow O(N\times N) = O(N^2)$

Even though it says at start we got $N$ elements, then we are deleting $Q(N)$ elements, here $Q(N)$ can be anything like $N/2,N/4,N/3$ and list need not be empty, then above explanation holds !

In case it actually deleted all elements at start analysis will be something like below $\Rightarrow$

All $N$ elements are deleted, Time complexity $O(1)$ each delete, total delete $O(N)$

Now $\log N$ insert, it'll take $1 + 2  + \log N$ time, then ($\log N * \log N-1)/2 \Rightarrow O((\log N)^2)$

Now $\log N$ finds $\Rightarrow$ it'll take $\log N$ time per find (because find take $O(N)$ but here $N = \log N$)
 $\Rightarrow O((\log N)^2)$

Now $N$ decrease key, Size of list is $\log N$, each decrease key can take $O(size \ of \ list)$

So, size of list * no. of decrease key $\Rightarrow N \times \log N = O(N \log N)$

There is no option like $O(N \log N)$

So, correct answer is $O(N^2)$.

Comments

What's your doubt bro?

---

For those having doubt in decrease-key, please note “We also need to keep the list sorted after each decrease key operation as it is a sorted DLL”.

That means, first it will take O(1) time to decrease then O(N) to insert.

---

It is a best explaination ...thanks @Akash Kanase

Answer 2

Delete - θ(1) time as pointer is directly given
Insert - O(N) time,we may need to insert at the end of the sorted list..
Find - θ(N) time.. list we need to search sequentially..
Decrease key - θ(N) time, pointer is directly given, delete then insert

Now using above..
θ(N) * θ(1) + O(logN) * O(N) + O(logN) * θ(N) + θ(N) * θ(N)
using property of asymptotic notation, and removing lower terms, we get O(N²)..
So Answer O(N²)     Option (C)

Answer 3

@as given in question

1. pointer is given to the node which has to be deleted so it takes O(1) time.

2. pointer to the node is given which has to be decreased so it takes O(1) time.

@things not given in the question we have to know them

3. findning a record takes O(N) time in avg case.

4. inserting a record takes O(N) time in avg case.

@now we have to perform the following  according to the question

1. O(N) delete

2. O(log N) insert

3. O(log N) find

4. O(N) decrease

so,

1. delete takes O(1)*O(N)=O(N)

2. insert takes O(log N)*O(N)=O(Nlog N)

3. find takes O(log N)*O(N)=O(NlogN)

4. decrease takes O(N)*O(1)=O(N)

so required ans will be [O(N)+O(NlogN)+O(NlogN)+O(N)] = O(NlogN)..

but no option matches so we take upper bound which happens to be O(N^2).

NOTE: if one of the option given is O(NlogN) then it should be the answer...

Comments

Decrease key operation will take O(N). Because pointer is provided, we decrease the key at that pointer and again we will delete this key from list and insert at right position so that resulting linked list remains sorted. In worst case you can consider this scenario

1)Every time pointer provided is last node of linked list.

2)modified (after decreasing the key) key is still largest among all nodes.

3) so when you insert it again, it will take O(N) comparisons.

so one decrease key operation will take O(N) time and we have O(N) such decrease key operations. 

so ans of Decrease key complexity is O(N)*O(N) = O(N²)

---

thanks man

Answer 4

this one will help you in understanding so visit this one also 

https://gateoverflow.in/8299/gate2015-1_40