FINAL EXAM BIG O CRAM

ArrayList add at first, add at last, add at any index

O(n) for add at first (must shift all elements right)
O(1)* for add at last (amortized append)
O(n) for add at any index (shift subsequent elements right)

ArrayList remove at first, remove at last, remove at any index

O(n) for remove at first (shift all elements left)
O(1) for remove at last (decrement size)
O(n) for remove at any index (shift subsequent elements left)

ArrayList search at index, search for specific value

O(1) for search at index (direct access)
O(n) for search for specific value (scan until found)

ArrayList resize

O(n) for resize (allocate new array and copy all elements)

SLL (no tail) add at first, add at last, add at any index

O(1) for add at first (update head)
O(n) for add at last (traverse to end)
O(n) for add at any index (traverse to position)

SLL (no tail) remove at first, remove at last, remove at any index

O(1) for remove at first (update head)
O(n) for remove at last (traverse to node before last)
O(n) for remove at any index (traverse to predecessor)

SLL (no tail) search at index, search for specific value

O(n) for search at index (must traverse node by node)
O(n) for search for specific value (must traverse node by node)

SLL (with tail) add at first, add at last, add at any index

O(1) for add at first (update head)
O(1) for add at last (update tail)
O(n) for add at any index (traverse)

SLL (with tail) remove at first, remove at last, remove at any index

O(1) for remove at first (update head)
O(n) for remove at last (traverse to predecessor)
O(n) for remove at any index (traverse to predecessor)

SLL (with tail) search at index, search for specific value

O(n) for search at index (must traverse node by node)
O(n) for search for specific value (must traverse node by node)

CSLL add at first, add at last, add at any index

O(1) for add at first (insert after tail)
O(1) for add at last (insert after tail and update tail)
O(n) for add at any index (traverse)

CSLL remove at first, remove at last, remove at any index

O(1) for remove at first (update tail.next)
O(n) for remove at last (traverse to predecessor)
O(n) for remove at any index (traverse to predecessor)

CSLL search at index, search for specific value

O(n) for search at index (must traverse node by node)
O(n) for search for specific value (must traverse node by node)

DLL (with tail) add at first, add at last, add at any index

O(1) for add at first (link before head)
O(1) for add at last (link after tail)
O(n) for add at any index (traverse)

DLL (with tail) remove at first, remove at last, remove at any index

O(1) for remove at first (unlink head)
O(1) for remove at last (unlink tail)
O(n) for remove at any index (traverse)

DLL (with tail) search at index, search for specific value

O(n) for search at index (must traverse)
O(n) for search for specific value (must traverse)

Stack (array-backed) add at last

O(1)* for push (amortized append)

Stack (array-backed) remove at last

O(1) for pop

Stack (array-backed) resize

O(n) when resizing on push

Queue (array-backed) add at last

O(1)* for enqueue (amortized in circular buffer)

Queue (array-backed) remove at first

O(1) for dequeue

Queue (array-backed) resize

O(n) when resizing

Deque (array-backed) add at first, add at last

O(1)* for add at first (amortized in circular buffer)
O(1)* for add at last (amortized in circular buffer)

Deque (array-backed) remove at first, remove at last

O(1) for remove at first
O(1) for remove at last

Deque (array-backed) resize

O(n) when resizing

BST add

O(log n) for add (traverse from root to insertion point)
O(n) for add in worst case (tree degenerates into a chain)

BST search

O(log n) for search (compare and traverse down the tree)
O(n) for search in worst case (unbalanced tree)

BST remove

O(log n) for remove (locate node, replace, and restructure)
O(n) for remove in worst case (degenerate tree)

Heap add

O(log n) for add (insert at end and bubble up)

Heap remove

O(log n) for remove (remove root, replace with last element, and bubble down)

HashMap with external chaining add

O(1) for add in average case (compute bucket and insert at head)
O(n) for add in worst case (all keys collide into one bucket)

HashMap with external chaining search

O(1) for search in average case (compute bucket and traverse short list)
O(n) for search in worst case (long collision list)

HashMap with external chaining remove

O(1) for remove in average case (compute bucket and unlink node)
O(n) for remove in worst case (long collision list)

HashMap with probing add

O(1) for add in average case (probe sequence to find empty slot)
O(n²) for add in worst case (table nearly full or long probe * n bad inserts)

HashMap with probing search

O(1) for search in average case (probe until match or empty)
O(n) for search in worst case (long probe sequence)

HashMap with probing remove

O(1) for remove in average case (probe to find and mark slot)
O(n) for remove in worst case (long probe sequence)

AVL add

O(log n) for add (BST insert + at most one or two rotations)

AVL search

O(log n) for search (balanced-tree traversal)

AVL remove

O(log n) for remove (BST delete + rotations to rebalance)

SkipList add

O(log n) for add in average case (random-level pointers)
O(n) for add in worst case (all nodes at level 1)

SkipList search

O(log n) for search in average case (multi-level traversal)
O(n) for search in worst case (degenerated levels)

SkipList remove

O(log n) for remove in average case (traverse levels and unlink)
O(n) for remove in worst case (degenerated levels)

2-4 Tree add

O(log n) for add (find leaf, insert, split nodes as needed)

2-4 Tree search

O(log n) for search (descend through 2–4 node keys)

2-4 Tree remove

O(log n) for remove (delete and rebalance via merge or redistribution)

Bubble sort best-case

O(n) when the list is already sorted (one pass, no swaps)

Bubble sort worst-case

O(n²) when the list is in reverse order (every pass swaps at every comparison)

Bubble sort stable/in-place/adaptive

Stable? Yes (preserves order of equal elements)
In-place? Yes (only needs constant extra space)
Adaptive? Yes (stops early if no swaps occur)

Insertion sort best-case

O(n) when the list is already sorted (each new element inserted with one comparison)

Insertion sort worst-case

O(n²) when the list is in reverse order (each insert shifts all prior elements)

Insertion sort stable/in-place/adaptive

Stable? Yes (preserves order of equal elements)
In-place? Yes (only needs constant extra space)
Adaptive? Yes (runs faster when input is partially sorted)

Selection sort best-case

O(n²) even when the list is sorted (always scans remaining elements to find min)

Selection sort worst-case

O(n²) when the list is in reverse or random order (same behavior as best)

Selection sort stable/in-place/adaptive

Stable? No (swapping may change order of equal elements)
In-place? Yes (only needs constant extra space)
Adaptive? No (performs same work regardless of initial order)

Cocktail shaker sort best-case

O(n) when the list is already sorted (one forward and backward pass, no swaps)

Cocktail shaker sort worst-case

O(n²) when the list is in reverse order (each pass moves one element)

Cocktail shaker sort stable/in-place/adaptive

Stable? Yes (like bubble sort, preserves equal-element order)
In-place? Yes (only needs constant extra space)
Adaptive? Yes (stops early if no swaps occur)

Merge sort best-case

O(n log n) for all inputs (always divides and merges)

Merge sort worst-case

O(n log n) for all inputs (same as best)

Merge sort stable/in-place/adaptive

Stable? Yes (merging preserves order of equal elements)
In-place? No (requires O(n) extra space for merging)
Adaptive? No (always performs full merge passes)

Quick sort best-case

O(n log n) with good pivot choices (balanced partitions)

Quick sort worst-case

O(n²) with poor pivot choices (highly unbalanced partitions)

Quick sort stable/in-place/adaptive

Stable? No (swapping may reorder equal elements)
In-place? Yes (partitioning uses constant extra space)
Adaptive? No (performance independent of initial order)

LSD radix sort best-case

O(n k) where n is number of elements and k is number of digit positions

LSD radix sort worst-case

O(n k) (same as best, processes all digits)

LSD radix sort stable/in-place/adaptive

Stable? Yes (uses stable sort per digit)
In-place? Yes (reuses small auxiliary structures)
Adaptive? No (always processes k digit passes)

Heap sort best-case

O(n log n) for all inputs (heapify and successive removals)

Heap sort worst-case

O(n log n) for all inputs (same as best)

Heap sort stable/in-place/adaptive

Stable? No (heap operations can reorder equal elements)
In-place? Yes (uses the array for the heap without extra space)
Adaptive? No (does the same work regardless of order)

Brute Force best cases

Best-case single occurrence: O(m) (pattern matches at first alignment)
Best-case all occurrences: O(n-m)* (first-character mismatches at every shift)

Brute Force worst cases

Worst-case single occurrence: O(nm) (each shift compares all m characters)
Worst-case all occurrences: O(nm) (worst-case overlaps at every alignment)

Boyer-Moore (no Galil Rule) best cases

Best-case single occurrence: O(m) (shifts by m on each mismatch)
Best-case all occurrences: O(n/m + m) (few comparisons per alignment)

Boyer-Moore (no Galil Rule) worst cases

Worst-case single occurrence: O(nm + m) (adversarial text/pattern)
Worst-case all occurrences: O(nm + m) (repeated worst-case alignments)

Boyer-Moore with Galil Rule best cases

Best-case single occurrence: O(m) (large shifts via bad-character heuristic)
Best-case all occurrences: O(n/m + m) (efficient skipping across all matches)

Boyer-Moore with Galil Rule worst cases

Worst-case single occurrence: O(nm + m) (bad-character-only worst case)
Worst-case all occurrences: O(nm + m) (no good-suffix, many overlaps)

KMP best cases

Best-case single occurrence: O(m) (prefix table avoids backtracking)
Best-case all occurrences: O(n + m) (single linear scan finds all)

KMP worst cases

Worst-case single occurrence: O(n + m) (guaranteed linear time)
Worst-case all occurrences: O(n + m) (still linear overall)

Rabin-Karp best cases

Best-case single occurrence: O(m) (constant-time hashes, no collisions)
Best-case all occurrences: O(n + m) (one pass with direct hash checks)

Rabin-Karp worst cases

Worst-case single occurrence: O(nm + m) (many hash collisions force rechecks)
Worst-case all occurrences: O(nm + m) (repeated collision-induced rechecks)

Adjacency Matrix (space complexity)

O(V^2) for best-worst

Adjacency List (space complexity)

O(V²) worst case; O(V + E) average

Edge List (space complexity)

O(E) for best-worst

Depth First Search (time complexity)

O(V + E), where V is the queue of vertices. Inefficient queues might increase V.

Breadth First Search (time complexity)

O(V + E), where V is the queue of vertices. Inefficient queues might increase V.

Dijkstra’s Algo (time complexity)

O(E log E)

Prim’s Algo (time complexity)

O(E log E)

Kruskal’s Algo (time complexity)

O(E log E)