The Gateway to Computer Science Excellence
+3 votes
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
(A) O(Log2N)
(B) O(N)
(C) O(N2)
(D) Θ(N2 Log N)

Doubt : What is decrease key? Decreasing the value?
and answer to the question.
in Programming by | 185 views
What does "time complexity of all these operations put together" mean?

total time complexity = $O(n)*O(1)+O(logn)O(n)+O(logn)*O(n)+O(n)*O(n)=O(n^2)$

so $O(n^2)$ is correct answer

How did u get this equation :o
i have simply multiplied cost of each operation with the no. of such operations and add all of them.
Ohh kk

For decrease key it's O(n)∗O(n) because decrease key will take Θ(N) and then to find it's new position to maintain list sorted, O(N), right?
to decrease a value of key it will take O(1) but to find its new place to fit, it will take O(n), so in total, cost of one decrease key operation is O(n)
Thanks :)

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,315 questions
60,427 answers
95,235 users