Week07 Complexity Analysis

Linear Search

Binary Search

Binary Search Trees

Dijkstra's Algorithm

Without a priority queue

Thus the time complexity is $O(V^2 + E)$, which is equivalent to $O(V^2)$

With priority queue

Dijkstra's Alogirthm with a priority queue

W3Schools.com

Relax's $O(E \log V)$

Each vertex is only "visited" (removed from the queue as the vertex with the shortest distance to the source) once. From observations we can find each edge is only checked once at most in Relax(). All $E$ edges will be checked, but only a portion of these operations trigger the shortest path update (priority queue update complexity of $O(\log V)$ )

Thus the time complexity is $O((E + V) \log V)$