1
Q
A
2
Q
Binary Search Best
A
Θ(1)
3
Q
Binary Search Average
A
Θ(logn)
4
Q
Binary Search Worst
A
Θ(logn)
5
Q
Binary Search Space
A
O(1)
6
Q
Binary Search Operation
A
Comparison (S[m]==key)
7
Q
Binary Search Notes
A
Requires data to be sorted and kept in RAM for random access.
8
Q
Hoare’s (QuickSelect) Best
A
Θ(n)
9
Q
Hoare’s (QuickSelect) Average
A
Θ(n)
10
Q
Hoare’s (QuickSelect) Worst
A
O(n2)
11
Q
Hoare’s (QuickSelect) Space
A
O(1)
12
Q
Hoare’s (QuickSelect) Operation
A
Comparing elements during Partition
13
Q
Hoare’s (QuickSelect) Notes
A
Finds the k-th positional statistic; much faster than repeated minimum search.
14
Q
Selection Sort Best
A
Θ(n2)
15
Q
Selection Sort Average
A
Θ(n2)
16
Q
Selection Sort Worst
A
Θ(n2)
17
Q
Selection Sort Space
A
O(1)
18
Q
Selection Sort Operation
A
Comparing two elements in an array
19
Q
Selection Sort Notes
A
Fixed number of operations regardless of initial data order.
20
Q
Insertion Sort Best
A
Θ(n)
21
Q
Insertion Sort Average
A
Θ(n2)
22
Q
Insertion Sort Worst
A
Θ(n2)
23
Q
Insertion Sort Space
A
O(1)
24
Q
Insertion Sort Operation
A
Comparing elements to find insertion point
25
Insertion Sort Notes
"Intelligent" and adaptive; performs linear time for already sorted data.
26
Merge Sort Best
Θ(nlogn)
27
Merge Sort Average
Θ(nlogn)
28
Merge Sort Worst
Θ(nlogn)
29
Merge Sort Space
Θ(n)
30
Merge Sort Operation
Comparing elements during Merge
31
Merge Sort Notes
Guaranteed linear-logarithmic time; stable sort.
32
QuickSort Best
Θ(nlogn)
33
QuickSort Average
Θ(nlogn)
34
QuickSort Worst
Θ(n2)
35
QuickSort Space
O(n)
36
QuickSort Operation
Comparing elements against the pivot
37
QuickSort Notes
Fastest practical sort; worst case occurs on sorted/invertedly sorted data.
38
Counting Sort Best
Θ(n+m)
39
Counting Sort Average
Θ(n+m)
40
Counting Sort Worst
Θ(n+m)
41
Counting Sort Space
Θ(n+m)
42
Counting Sort Operation
Placing a value into an array
43
Counting Sort Notes
Non-comparison sort; linear time but requires high space.
44
Unbounded Array (Push) Best
O(1)
45
Unbounded Array (Push) Average
O(1)
46
Unbounded Array (Push) Worst
O(n)
47
Unbounded Array (Push) Space
Θ(n)
48
Unbounded Array (Push) Operation
Copying elements during reallocation
49
Unbounded Array (Push) Notes
Constant amortized time via doubling and copying strategy.
50
Binary Heap (Insert) Best
O(1)
51
Binary Heap (Insert) Average
O(logn)
52
Binary Heap (Insert) Worst
O(logn)
53
Binary Heap (Insert) Space
O(n)
54
Binary Heap (Insert) Operation
Comparison and swap with parent (upheap)
55
Binary Heap (Insert) Notes
Fast construct of a heap from a sequence takes Θ(n).
56
Binary Search Tree Best
O(1)
57
Binary Search Tree Average
O(logn)
58
Binary Search Tree Worst
O(n)
59
Binary Search Tree Space
Θ(n)
60
Binary Search Tree Operation
Comparison with node keys
61
Binary Search Tree Notes
Simple ordered dictionary; worst case if tree is unbalanced (linear chain).
62
Hashtable Best
O(1)
63
Hashtable Average
O(1)
64
Hashtable Worst
Θ(n)
65
Hashtable Space
Θ(n)
66
Hashtable Operation
Hash calculation and key comparison
67
Hashtable Notes
Very fast dictionary operations but no support for ordering operations (e.g.; Min).
68
BFS / DFS Best
Θ(V+E)
69
BFS / DFS Average
Θ(V+E)
70
BFS / DFS Worst
Θ(V+E)
71
BFS / DFS Space
Θ(V)
72
BFS / DFS Operation
Visiting vertices and exploring edges
73
BFS / DFS Notes
BFS finds shortest paths in unweighted graphs.
74
Dijkstra's Best
O(ElogV)
75
Dijkstra's Average
O(ElogV)
76
Dijkstra's Worst
O(ElogV)
77
Dijkstra's Space
Θ(V)
78
Dijkstra's Operation
Priority Queue operations (delMin)
79
Dijkstra's Notes
Requires non-negative edge weights.
80
Bellman-Ford Best
Θ(V⋅E)
81
Bellman-Ford Average
Θ(V⋅E)
82
Bellman-Ford Worst
Θ(V⋅E)
83
Bellman-Ford Space
Θ(V)
84
Bellman-Ford Operation
Edge relaxation
85
Bellman-Ford Notes
Handles negative weights and detects negative cycles.
86
Prim's / Kruskal's Best
O(ElogV)
87
Prim's / Kruskal's Average
O(ElogV)
88
Prim's / Kruskal's Worst
O(ElogV)
89
Prim's / Kruskal's Space
Θ(V)
90
Prim's / Kruskal's Operation
PQ operations (Prim) / Edge sorting (Kruskal)
91
Prim's / Kruskal's Notes
Kruskal's is often faster for sparse graphs where E=O(V).
92
Algorithm/Operation Property
Complexity/Value
93
Indexing [.] Singly Linked List (SList)
O(n)
94
Indexing [.] Doubly Linked List (DList)
O(n)
95
Indexing [.] Unbounded Array (UArray)
O(1)
96
Indexing [.] Cyclic Array (CArray)
O(1)
97
First/Last Singly Linked List (SList)
O(1)
98
First/Last Doubly Linked List (DList)
O(1)
99
First/Last Unbounded Array (UArray)
O(1)
100
First/Last Cyclic Array (CArray)
O(1)
101
Insert/Remove Singly Linked List (SList)
O(1) (relative)
102
Insert/Remove Doubly Linked List (DList)
O(1) (relative)
103
Insert/Remove Unbounded Array (UArray)
O(n)
104
Insert/Remove Cyclic Array (CArray)
O(n)
105
PushBack Singly Linked List (SList)
O(1)
106
PushBack Doubly Linked List (DList)
O(1)
107
PushBack Unbounded Array (UArray)
O(1) (amortised)
108
PushBack Cyclic Array (CArray)
O(1) (amortised)
109
PushFront Singly Linked List (SList)
O(1)
110
PushFront Doubly Linked List (DList)
O(1)
111
PushFront Unbounded Array (UArray)
O(n)
112
PushFront Cyclic Array (CArray)
O(1) (amortised)
113
PopBack Singly Linked List (SList)
O(n)
114
PopBack Doubly Linked List (DList)
O(1)
115
PopBack Unbounded Array (UArray)
O(1) (amortised)
116
PopBack Cyclic Array (CArray)
O(1) (amortised)
117
PopFront Singly Linked List (SList)
O(1)
118
PopFront Doubly Linked List (DList)
O(1)
119
PopFront Unbounded Array (UArray)
O(n)
120
PopFront Cyclic Array (CArray)
O(1) (amortised)
121
Splice Singly Linked List (SList)
O(1)
122
Splice Doubly Linked List (DList)
O(1)
123
Splice Unbounded Array (UArray)
O(n)
124
Splice Cyclic Array (CArray)
O(n)
125
Property
Value
126
Unsorted List/Array insert Best Case
O(1)
127
Unsorted List/Array insert Average Case
O(1)
128
Unsorted List/Array insert Worst Case
O(1)
129
Unsorted List/Array insert Space Complexity
Θ(n)
130
Unsorted List/Array findMin Best Case
Θ(n)
131
Unsorted List/Array findMin Average Case
Θ(n)
132
Unsorted List/Array findMin Worst Case
Θ(n)
133
Unsorted List/Array findMin Space Complexity
-
134
Unsorted List/Array delMin Best Case
Θ(n)
135
Unsorted List/Array delMin Average Case
Θ(n)
136
Unsorted List/Array delMin Worst Case
Θ(n)
137
Unsorted List/Array delMin Space Complexity
-
138
Sorted List/Array insert Best Case
O(n)
139
Sorted List/Array insert Average Case
Θ(n)
140
Sorted List/Array insert Worst Case
Θ(n)
141
Sorted List/Array insert Space Complexity
Θ(n)
142
Sorted List/Array findMin Best Case
O(1)
143
Sorted List/Array findMin Average Case
O(1)
144
Sorted List/Array findMin Worst Case
O(1)
145
Sorted List/Array findMin Space Complexity
-
146
Sorted List/Array delMin Best Case
O(1)
147
Sorted List/Array delMin Average Case
O(1)
148
Sorted List/Array delMin Worst Case
O(1)
149
Sorted List/Array delMin Space Complexity
-
150
Binary Heap insert Best Case
O(1)
151
Binary Heap insert Average Case
O(logn)
152
Binary Heap insert Worst Case
O(logn)
153
Binary Heap insert Space Complexity
Θ(n)
154
Binary Heap findMin Best Case
O(1)
155
Binary Heap findMin Average Case
O(1)
156
Binary Heap findMin Worst Case
O(1)
157
Binary Heap findMin Space Complexity
-
158
Binary Heap delMin Best Case
O(logn)
159
Binary Heap delMin Average Case
O(logn)
160
Binary Heap delMin Worst Case
O(logn)
161
Binary Heap delMin Space Complexity
-
PJATK
flashcards
Decks in class (28)
# Cards
