Test series

Question

Consider unsorted doubly linked list data structure containing n items. For decrease key operation a pointer is provided to the record on which the operation is performed. An algorithm performs the following operations on the list in this order: sqrt(n) insert operations, o(nlogn) decrease key and O(n) find operations. What is the time complexity of all these operations put together?

(a) O(n)

(b) O(n2)

(c) O(n2logn)

(d) O(sqrt(n))

Comments

@Somoshree Datta 5

For decrease key operation a pointer is provided to the record on which the operation is performed

We are already provided with the pointer to the node whose value needs to be decreased so we don't need to worry about it's presence.

---

@MiniPanda if pointer wouldnt have been provided, then both for sorted lists as well as unsorted lists decrease key operation would take O(n) time right?

---

@Somoshree Datta 5

Yes..

Answer 1

For unsorted doubly linked list :

Insert - O(1)

decrease key - O(1) 

find - O(n)

total = √n *O(1) + nlogn*O(1) +  n* O(n) = O(n²)