The following algorithms and data structures from 332 can be used without any further explanation.

- Quicksort:
- Worst-case time O(n^2)
- Average-case time O(n log n)
- In-place, but not stable; usually fastest in “the real world”

- Mergesort:
- Worst-case time O(n log n)
- Average-case time O(n log n)
- not in-place, but stable

- Heapsort:
- Worst-case time O(n log n)
- Average-case time O(n log n)
- in-place, but not stable.

- Dijkstra’s Algorithm:
- Running time: O(E log V + V log V)
- Precondition: All edge-weights non-negative.
- Stores distance from source to v in v.dist for every vertex v.
- Can also find path from source to v for a particular v in O(E) extra time.

- BFS-Shortest Path:
- Running time: O(V+E)
- Precondition: All edge weights are identical (or unweighted).
- Stores distance from source to v in v.dist for every vertex v.
- Can also find path from source to v for a particular v in O(E) extra time.

- Kruskal’s Algorithm:
- Running time: O(E log E)
- Returns list of edges in MST or a graph object containing just the spanning tree.

- Prim’s Algorithm:
- Running time: O(E + V log V)
- Returns list of edges in MST or a graph object containing just the spanning tree.

[B/D]FS modification to find connected components.

- Running Time O(V+E)
- Precondition: undirected graph.
- Stores a component number in each vertex (given two vertices, the numbers are the same if-and-only-if they are in the same component)

[B/D]FS modification to find weakly connected components.

- Running Time O(V+E)
- Precondition: directed graph.
- Stores a component number in each vertex (given two vertices, the numbers are the same if-and-only-if they are in the same weakly connected component)

DFS modification to find strongly connected components.

- Running time: O(V+E)
- Precondition: directed graph.
- Stores a SCC number in each vertex (given two vertices, the numbers are the same if-and-only if they are in the same strongly connected component)

DFS modification to find meta-graph (a.k.a. “condensation graph”) of G.

- Running time: O(V+E) (of the original graph
- Precondition: directed graph.
- Given vertex u of G, can get access in constant time to corresponding component vertex of condensation graph.
- Given component vertex of condensation graph, can get (in constant time) a list of the vertices of G in that component.

DFS modification to find topological sort.

- Running time O(V+E)
- Precondition: directed acyclic graph.
- Stores the index in the ordering in each vertex (e.g. if u is the 3rd vertex in the list, u has 3 stored inside) or returns a list of vertices in order.

AVL tree

Operation Worst-case Average-Case Insert O(log n) O(log n) Find O(log n) O(log n) Delete O(log n) O(log n) -
Hash Table

Operation Worst-case Average-Case Insert O(n) O(1) Find O(n) O(1) Delete O(n) O(1) - If you can guarantee a constant number of collisions (for example, because you know the keys in advance), all worst-case times become O(1).

ArrayList

Operation Worst-case Average-Case Insert at front O(n) O(n) Insert at end O(1) (amortized) O(1) Delete O(n) O(n) Find O(log n) if sorted, O(n) otherwise O(log n) if sorted, O(n) otherwise - In some use-cases, some of these operations can be sped up (for example, if you use lazy deletion, in a sorted array, deletion can be sped up)

Linked List

Operation Worst-case Average-Case Insert at front O(1) O(1) Insert at end O(1) O(1) Delete O(n) O(n) Find O(n) O(n)

Operation | Running time (worst- and average-case) |
---|---|

Enqueue | O(1) |

Peek | O(1) |

Dequeue | O(1) |

- Running times are amortized for array-based implementations.

Operation | Running time (worst- and average-case) |
---|---|

Push | O(1) |

Peek | O(1) |

Pop | O(1) |

- Running times are amortized for array-based implementations.

Operation | Running time (worst- and average-case) |
---|---|

Insert | O(log n) |

Remove-Min | O(log n) |

Peek-Min | O(1) |

Decrease Priority | O(log n) |

Build-Heap (create heap with n elements) | O(n) |