CS3 Runtimes
Call Kai
Learn
Practice Test
Spaced Repetition
Match
Flashcards
Knowt Play1/12
There's no tags or description
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced | Call with Kai |
|---|
No analytics yet
Send a link to your students to track their progress
13 Terms
What is the big-Oh run time of Merge Sort on n items?
O(n log n)
What is the big-Oh run time of Heap Sort on n items?
O(n log n)
What is the worst case big-Oh run time to insert 1 item into a min-heap?
O(log n)
What is the big-Omega lower bound for comparison based sorting of n items?
Ω(n log n)
What is the worst case big-Oh run time to insert 1 item into an AVL-tree that contains n items?
O(log n)
What is the worst case big-Oh run time of binary search on an n item sorted list?
O(log n)
What is the worst case big-Oh run time to remove the minimum value from a min-heap?
O(log n)
What is the run time of breadth-first search (in terms of |V| and |E|)?
O(|V| + |E|)
What is the run time of Dijkstra’s algorithm (in terms of |V| and |E|) assuming a min-heap based implementation?
O((|V| + |E|) log |V|)
What is the run time of Dijkstra’s algorithm (in terms of |V| and |E|) assuming a Fibonacci heap based implementation?
O(|E| + |V| log |V|)
What is the run time of the Bellman-Ford single-source shortest path algorithm (in terms of |V| and |E|)?
O(|V| · |E|)
What is the run time of the Floyd-Warshall “all-pairs” shortest path algorithm (The one that uses dynamic programming)?
O(|V|³)
What is the run time of the Edmonds-Karp maximum flow algorithm?
O(|V| · |E|²)