The Gateway to Computer Science Excellence
+2 votes
159 views
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 Loyal (7.8k points) | 159 views
0
yes.
0
What does "time complexity of all these operations put together" mean?
+2

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

0
How did u get this equation :o
+1
i have simply multiplied cost of each operation with the no. of such operations and add all of them.
0
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?
+1
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)
0
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
50,647 questions
56,492 answers
195,439 comments
100,694 users