GATE 2016 CS (CS2) – Question 25
N records are in a sorted doubly linked list. Node pointers are supplied for delete and decrease-key. An algorithm performs, in order, $\Theta(N)$ deletes, $O(\log N)$ inserts, $O(\log N)$ finds, and $\Theta(N)$ decrease-key operations. What is their combined time complexity?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) $O(N^2)$
Explanation
A delete takes constant time with its pointer. Finding a key or an insertion position can take linear time. Decrease-key may require linear traversal to relocate the record and maintain sorted order. The Θ(N) decrease-key operations dominate at O(N²); the logarithmically many searches/inserts contribute O(N log N). Thus C.