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

@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