Algorithm Complexities Flashcards
1
Q
Insertion Sort
A
Best Case: O(n)
Worst Case: O(n^2)
Average: O(n^2 / 2)
2
Q
Selection Sort
A
O(n^2 / 2)
3
Q
Merge Sort
A
O(n log n)
4
Q
Quick Sort
A
O(n log n)
5
Q
Heap Sort
A
O(n log n)
6
Q
Sequential Search
A
O(n/2)
7
Q
Binary Search
A
O(log n)
8
Q
Binary Search Tree
A
Worst Case: O(n)
Average: O(1.39 log n)
9
Q
Red-Black Search Tree
A
O(log n)
10
Q
Depth-First Search
A
O(E)
11
Q
Breadth-First Search
A
O(V+E)
12
Q
Prim’s MST Algorithm
A
O(E log E)
13
Q
Kruskal’s MST Algorithm
A
O(E log E)
14
Q
Dijkstra’s Shortest-Path Algorithm
A
O(E log V)
15
Q
Longest Path in DAG
A
O(E + V)
16
Q
Bellman-Ford
A
O(EV)
17
Q
Ford-Fulkerson
A
O(VE^2 / 2)
18
Q
Stable Matching
A
O(n^2)
19
Q
A*
A
Roughly same as Dijkstra’s, though slightly better: O(E log V)
20
Q
Memoization
A
Saving values that have already been calculated - part of dynamic programming
