3
$\begingroup$

Using a heap, you have O(log(n)) insertion and O(log(n)) removal. Using a linked list, you have O(n) insertion and O(1) removal.

Why is it better to have log-n for both than n for one and constant time for the other?

Improve this question
$\endgroup$
1
  • $\begingroup$ Why would the opposite be true ?? $\endgroup$
    – Yves Daoust
    Dec 30, 2022 at 16:45

2 Answers 2

Reset to default
3
$\begingroup$

It only really matters in the limit: for small sizes, the difference isn't really important.

But if you're doing a large number of each operation, $O(\log n) + O(\log n) = O(\log n)$ is asymptotically faster than $O(n) + O(1) = O(n)$.

Improve this answer
$\endgroup$
1
$\begingroup$

We have a simple equation: Number of insertions = number of removals + size of priority queue. If the number of insertions is n, then the heap will be faster as long as the number of removals is at least n / log n. And if the number of removals isn't that large, then your priority queue will grow in size very, very quickly.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.