Consider the following algorithms and their running times. Match each…

Concept

Each algorithm has a characteristic worst-case asymptotic running time determined by how much work it does relative to its input. Graph traversals are bounded by the size of the graph (vertices + edges); string matching and comparison sorts are bounded by the input/pattern sizes. The key distinctions to keep straight are: BFS and DFS both touch every vertex and edge a constant number of times; a comparison sort cannot beat O(n lg n); and quick sort, unlike heap sort, can degrade on a bad pivot.

Applying it to each algorithm

• Breadth First Search — visits every vertex and traverses every edge a constant number of times, so its running time is O(V + E).

• Depth-First Search — like BFS, processes each vertex and edge a constant number of times, giving Θ(V + E).

• Rabin–Karp Algorithm — in the worst case the rolling hash produces a match at many alignments, forcing a full character comparison of length m at each, which costs Θ((n − m − 1)m).

• Heap sort (worst case) — building the heap and performing n extract-max operations, each O(lg n), gives O(n lg n) even in the worst case (it has no bad-pivot failure mode).

• Quick sort (worst case) — with a consistently poor pivot (e.g. already-sorted input with first/last pivot) the partition sizes are maximally unbalanced, degrading to O(n2).

Correct mapping

Cross-check

The two graph algorithms take the two graph bounds (V + E), the single string-matching algorithm takes the only quadratic-in-(n,m) bound, and the two comparison sorts split between O(n lg n) and O(n2) — heap sort is guaranteed O(n lg n) while quick sort alone has a quadratic worst case. This consistent assignment matches exactly one of the offered options.