FoundationsSheet 1 of 2
Algorithms10 concepts
Big-O Complexity
1
O(1) — Constant
Hash table lookup, array index access, stack push/pop.
2
O(log n) — Logarithmic
Binary search, balanced BST lookup, skip list search.
3
O(n) — Linear
Array scan, linked list traversal, hash table resize.
4
O(n log n) — Linearithmic
Merge sort, heap sort, quicksort (average). Optimal comparison sort.
5
O(n²) — Quadratic
Bubble sort, insertion sort (worst), naive matrix multiply inner loop.
6
Array (sorted)
Access O(1), Search O(log n), Insert O(n), Delete O(n).
7
Linked List
Access O(n), Search O(n), Insert O(1) at head, Delete O(1) with pointer.
8
Hash Table
Access N/A, Search O(1) avg, Insert O(1) avg, Delete O(1) avg.
9
BST (balanced)
Access O(log n), Search O(log n), Insert O(log n), Delete O(log n).
10
Heap
Find min/max O(1), Insert O(log n), Delete min/max O(log n).