Runtimes Flashcards
1
Q
Bubble Sort Best Case
A
O(n)
2
Q
Bubble Sort Average Case
A
O(n^2)
3
Q
Bubble Sort Worst Case
A
O(n^2)
4
Q
Binary Search Best Case
A
O(1)
5
Q
Binary Search Average Case
A
O(n^2)
6
Q
Binary Search Worst Case
A
O(n^2)
7
Q
Insertion Sort Best Case
A
O(n)
8
Q
Insertion Sort Average Case
A
O(n^2)
9
Q
Insertion Sort Worst Case
A
O(n^2)
10
Q
Selection Best Case
A
O(n^2)
11
Q
Selection Sort Average Case
A
O(n^2)
12
Q
Selection Sort Worst Case
A
O(n^2)
13
Q
Quick Sort Best Case
A
O(nlgn)
14
Q
Quick Sort Average Case
A
O(nlgn)
15
Q
Quick Sort Worst Case
A
O(n^2)
16
Q
Merge Sort Best Case
A
O(nlgn)
17
Q
Merge Sort Average Case
A
O(nlgn)
18
Q
Merge Sort Worst Case
A
O(nlgn)
19
Q
Dynamic Array AddBack Best Case
A
O(1)
20
Q
Dynamic Array AddBack Average Case
A
O(1)
21
Q
Dynamic Array AddBack Worst Case
A
O(n)
22
Q
Dynamic Array RemoveBack Best Case
A
O(1)
23
Q
Dynamic Array RemoveBack Average Case
A
O(1)
24
Q
Dynamic Array RemoveBack Worst Case
A
O(n)
25
Open Addressing Functions Best Case
O(1)
26
Open Addressing Functions Average Case
O(1)
27
Open Addressing Functions Worst Case
O(n)
28
Separate Chaining Best Case
O(1)
29
Separate Chaining Average Case
O(1)
30
Separate Chaining Worst Case
O(n)
31
Binary Search Tree Find/Insert Best Case
O(1)
32
Binary Search Tree Find/Insert Average Case
O(lgn)
33
Binary Search Tree Find/Insert Worst Case
O(n)
34
Static list insert front/back
O(n)
35
Static list remove front/back
O(n)
36
Singly-linked circular list w/ head/tail pointers insert front
O(1)
37
Singly-linked circular list w/ head/tail pointers insert back
O(1)
38
Singly-linked circular list w/ head/tail pointers remove front
O(1)
39
Singly-linked circular list w/ head/tail pointers remove back
O(n)
40
Heap insert
O(lgn)
41
Heap sort
O(nlgn)
42
Heapify
O(n)
43
Heap Extract
O(lgn)
44
BFS Adj Matrix
O(V^2)
45
DFS Adj Matrix
O(V^2)
46
Dijkstras Adj Matrix
O(V^2)
47
BFS Adj List
O(V+E)
48
DFS Adj List
O(V+E)
49
Dijsktras Adj List
O(ElgV)
50
Prim's Adj Matrix
O(V^2)
51
Prim's Adj List
O(ElgV)
52
Kruskal's Disjointed Set
O(ElgV)
53
Union by Height/Size Constructor
O(n)
54
Union by Height/Size Merge
O(1)
55
Union by Height/Size Find
O(h)->O(lgn)
56
