Question: In our analysis of Dijkstra's priority-first search algorithm we used a heap implementation of a priority queue. How long would a search take if we used an unordered list implementation instead? (Do version 2 of the algorithm, where the ants have calculators and we occassionally decrease priorities. We'll want an array indexing where the vertices are in the list so that we can decrease a priority in constant time.) What if we used a list ordered by priority?
Answer: With an unordered list, each insert takes O(1) item, each change of priority takes O(1) time, and each removal takes O(k) time, where k is the size of the queue. In version 2 of Dijkstra's algorithm the queue always has at most n elements. There are n removals and m insertions and priority changes. So the total amount of time is O(n^2 + m) = O(n^2).
With an ordered list an insert or priority change takes O(k) time, and a removal takes O(1) time. So the total time taken is O(n + mn) = O(mn).