Follow Us :

PA of Algorithms Q75

75N 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?
  • Option : C
  • Explanation :
    Delete operation require O(1) time total O(N) Delete so time is = O(n).
    Insert require O(n) time in worst case total O (logn) insert so time is = O(Nlogn) to Search (logn) key time is = nlogn.
    To perform decrease key we need O (n) time (because after decrease we need to arrange elements in sorted sequerce) so total O(N) decrease key So total time is O(N2) All operations put together than worst time is O(N2)
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *