| Linear Search | $O(n)$ |
|---|---|
| Binary Search | $O(log \space n)$ |
| Breadth First Search | $O(V + E)$ |
| Depth First Search | $O(V + E)$ |
| Insertion Sort | $O(n^2)$ |
|---|---|
| Selection Sort | $O(n^2)$ |
| Merge Sort | $O(n \space log \space n)$ |
| Quick Sort | $O(n \space log \space n)$ |
| In average case, if pivot is randomly chosen. | |
| $O(n^2)$ | |
| In worst case, if pivot is determinstic. | |
| Radix Sort | $O(n)$ |
| | append()
prepend() | insert() | delete() | find() |
| --- | --- | --- | --- | --- |
| Arrays | $O(n)$ | $O(n)$ | $O(n)$ | $O(n)$ |
| Sorted Arrays | $O(n)$ | $O(n)$ | $O(n)$ | $O(log \space n)$ |
| Linked Lists | $O(1)$ | $O(1)$ | | $O(n)$ |
| Stacks | | $O(1)$ | $O(1)$ | |
| Queues | | $O(1)$ | $O(1)$ | |
| Prority Queues (Heaps) | | $O(log \space n)$ | $O(log \space n)$ | $O(log \space n)$ |
| Binary Search Trees | | $O(tree \space height)$ | $O(tree \space height)$ | $O(tree \space height)$ |
| AVLs | | $O(log \space n)$ | $O(log \space n)$ | $O(log \space n)$ |
| Splays | | $O(log \space n)$ | $O(log \space n)$ | $O(log \space n)$ |
| Worst Case Height | Best Case Height |
|---|---|
| $log_t \space n$ | $log_M \space n$ |
find() |
union() |
|
|---|---|---|
| Fast Find | $O(1)$ | $O(n)$ |
| Quick Union | $O(n)$ | $O(n)$ |
| Weighted Union | $O(log \space n)$ | $O(log \space n)$ |
| Kruskal’s Algorithm | $O(E \space log \space V)$ |
|---|
| Determining if 2 given nodes are in the edge set $E$ | |
|---|---|
| Adjacency Matrix | $O(1)$ |
| Adjacency List | $O(n)$ |
| Operation | Hash Table (w/ chaining) | Hash Table (no chaining) |
|---|---|---|
insert() |
$O(n)$ | $O(1)$ |
search() |
$O(n)$ | $O(1)$ |