Runtimes of Graphs

what is the runtime general formula for dijkstras/prims? What do you do to each phrase/word?

VExtractions + EUpdates + Read Graph

extractions and updates are considered whether it’s a heap or array

read graph is based on adj. list (sparse or dense) or matrix

what happens to updates and extractions when we are dealing with a heap?

logV for both

what happens to extractions and updates when its an array ?

extractions = V so V*V

updates = o(1) so EO(1)

what happens to adj list when sparse? dense?

V + E for sparse

V² for Dense

what is the runtime of both BFS AND DFS?

V+E for List

v² for Matrix

Runtime for bellman?

o(VE) for list

O(V³) for matrix

what is kruskals general formula?

ElogE (sorting) + E(Find) + V(Unions)

usually both logV for find and union

= ElogE

what is the runtime for PRIMS/D when ir’s an array/adj.list or matrix ? = o(v²)

runtime for prims or dijkstras when it’s heap and list/matrix

ELogV for list

ELogE + V² for matrix