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)
