1
GATE CSE 2016 Set 2
+1
-0.3
$$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\left( {\log N} \right)\,insert,\,$$ $$\,O\left( {\log N} \right)\,fund, and$$ $$\Theta \left( N \right)\,$$ $$decrease$$-$$key.$$ What is the time complexity of all these operations put together?

A
$$O\left( {{{\log }^2}N} \right)$$
B
$$O\left( N \right)$$
C
$$O\left( {{N^2}} \right)$$
D
$$\Theta \left( {{N^2}\log N} \right)$$
2
GATE CSE 2004
+1
-0.3
Let P be a singly linked list, Let Q be the pointer to an intermediate node x in the list.What is the worst-case time complexity of the best known algorithm to delete the node x from the list?
A
O(n)
B
O(log2n)
C
O(log n)
D
O(1)
3
GATE CSE 2002
+1
-0.3
In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
A
log2 n
B
n/2
C
log2 n − 1
D
n
GATE CSE Subjects
EXAM MAP
Medical
NEET