Previous Lecture

lect17

Next Lecture

lect17,

Complexity Analysis Revisited: Graph Search and std::set

Topics

Complexity of Graph Search

• BFS and DFS both run in O(V + E) — why?
  • Every vertex is visited once (V)
  • Every edge is examined once (E)
  • Representation matters: adjacency list vs adjacency matrix
• Space complexity: BFS uses a queue (O(V)), DFS uses the call stack (O(V))

Complexity of Mergesort

• Divide: O(log n) levels of recursion
• Conquer: O(n) work at each level
• Total: O(n log n) — compare to O(n²) for insertion/selection sort

BST Iteration with std::set

• std::set is implemented as a balanced BST
• Iterating over a std::set in order is an in-order DFS traversal
• In-order traversal runs in O(n) — visits every node exactly once
• Connecting iterator behavior to the underlying graph structure

Code from lecture

https://github.com/ucsb-cs24-w26/cs24-w26-lectures/tree/main/lect17