Bissoy.com
Doctors Medicines MCQs Q&A

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: Θ(N) delete, O(log N) insert, O(log N) find, and Θ(N) decrease-key. What is the time complexity of all these operations put together?

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: Θ(N) delete, O(log N) insert, O(log N) find, and Θ(N) decrease-key. What is the time complexity of all these operations put together? Correct Answer O(N<sup>2</sup>)

Here, it is given that pointer is provided to the record on which the decrease key operation is to be performed. So, time complexity of decrease key operation is Θ (1)

For insert – Θ (N), we need to insert the element at the end of the sorted list.

For delete – Θ (1) time is needed, as pointer is directly given

For decrease key – Θ (N), because after decreasing the key value, all the elements must be sorted again.

Now combining all the operations together:

For delete = Θ (N)* Θ (1)

For insert = Θ (log N)*Θ (N)

For find = Θ (log N)*Θ (N)

For decrease-key = Θ (N)* Θ (N)

So, overall complexity = Θ (N)* Θ (1 ) + Θ (logN)* Θ (N) + Θ (logN)* Θ (N)+ Θ (N)* Θ (N)

Time complexity of all these operations put together = Θ (N2)

Related Questions

In an adjacency list representation of an undirected simple graph G = (V, E), each edge (u, v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E| = m and |V| = n, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?
Post office protocol (POP) is a message access protocol which is used to extract message for client. In this regard, which of the following are true ? (A) POP has two modes, Delete mode and keep (B) In Delete mode, mail is deleted from mail box after each retrival (C) In Delete mode, mail is deleted from mail box before each retrieval (D) In keep mode, mail is deleted before retrival (E) In keep mode, mail remains in mail box after retrival Choose the correct answer from the options given below:
Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not given, can we delete the node X from given linked list?
Consider a singly linked list of the form where F is a pointer to the first element in the linked list and L is the pointer to the last element in the list. The time of which of the following operations depends on the length of the list?
A doubly linked list is declared as struct Node{                 int Value;                 struct Note*fwd;                 struct Node * Bwd; } Where Fwd and Bwd represent forward and backward link to the adjacent elements of the list. Which of the following segments of code deletes the node pointed to by X from the doubly liked list, if it is assumed that X points to neither the first nor the last node of the list?
A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the near node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in O(1) time? I. Next pointer of front node points to the rear node. II. Next pointer of rear node points to the front node.
City High School must put together a debating team consisting of four debaters.There are candidates of equal ability : X,Y and Z who are all seniors; and A,B,C and D who are all juniors..The school requires that there should be two seniors and two juniors in the team.It is also necessary that all of the debaters be able to work with one another. *Debaters Y and A cannot work together. *Debaters Z and C cannot work together. *Debaters A and B cannot work together. which of the following statements must be false? 1.Debaters Y and C are never selected together. 2.Debaters Z and D are never selected together. 3.Debaters Z and D are never selected together.
What is the time complexity of insert function in a hash table using a doubly linked list?
Consider the problem of reversing a singly linked list. To take an example, given the linked list below, the reversed linked list should look like Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?
What is the time complexity of delete function in the hash table using a doubly linked list?