yes.

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.

Θ(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.

+3

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

+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?

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?

52,315 questions

60,427 answers

201,756 comments

95,235 users