Discussion
\(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(N)\) 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?
Answer: C
The total time is \(O(N^{2})\).
Cost each batch on a sorted doubly linked list:
- \(\Theta(N)\) deletes: with a pointer to the node, each is \(O(1)\), so \(O(N)\) in all.
- \(O(\log N)\) inserts: finding the position in a sorted list takes \(O(N)\) each, so \(O(N\log N)\).
- \(O(\log N)\) finds: a linear search each, \(O(N\log N)\).
- \(\Theta(N)\) decrease-keys: the node is reached by pointer, but its new smaller key may belong much further forward, and moving it there takes \(O(N)\) each, so \(O(N^{2})\).
The decrease-keys dominate, giving \(O(N^{2})\). \(O(N)\) ignores the cost of repositioning, \(O(\log^{2}N)\) assumes logarithmic operations a linked list cannot provide, and \(\Theta(N^{2}\log N)\) overstates the bound.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development