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?
$\begingroup$
$\endgroup$
1
asked Jan 13, 2019 at 22:26
-
$\begingroup$ Why would the opposite be true ?? $\endgroup$– user16034Commented Dec 30, 2022 at 16:45
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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)$.
$\begingroup$
$\endgroup$
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.
