(This is an algorithm design question) For the worst-case time complexity of the

Question

(This is an algorithm design question)

For the worst-case time complexity of the three basic priority queue operations (insert, find-minimum, and delete-minimum) when the basic data structure is an unsorted array, I don't understand the explanation given for delete-minimum.

In particular, it says a linear time implementation of delete-minimum can be composed from find-minimum, followed by search, followed by delete.

Surely the second search query is unnecessary?

Would appreciate a beginner's explanation to clarify for the above.

Thank You

Explanation / Answer

I think it is referring to Normal delete and not delete-min,

delete min is always O(log n) and does not require any search operation to be performed , hence the time is logarithmic

delete() : Is Linear time because we have to find out the element is at which location that itself takes O(N) time and then we perform delete which takes O(log N), so Overall it is a linear time algorithm.


Thanks, let me know if you require any more clarification.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.