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?

$\endgroup$
1
  • $\begingroup$ Why would the opposite be true ?? $\endgroup$
    – user16034
    Dec 30, 2022 at 16:45

2 Answers 2

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)$.

$\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.

$\endgroup$

Your Answer

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

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