Big-O Cheatsheet for CS Students

// Java ArrayList: amortized O(1) append, O(n) insert at index
import java.util.ArrayList;

ArrayList<Integer> nums = new ArrayList<>();
nums.add(3);          // O(1) amortized
nums.add(0, 7);       // O(n), shifts every element right
int first = nums.get(0); // O(1) random access
nums.remove(0);       // O(n), shifts every element left
boolean found = nums.contains(3); // O(n), linear scan

# Python list: amortized O(1) append, O(n) insert at index
nums = []
nums.append(3)        # O(1) amortized
nums.insert(0, 7)     # O(n), shifts every element right
first = nums[0]       # O(1) random access
del nums[0]           # O(n), shifts every element left
found = 3 in nums     # O(n), linear scan
# Gotcha: nums[1:] copies the tail (O(n)), not free slicing.

// C++ std::vector: amortized O(1) push_back, O(n) insert at index
#include <vector>
#include <algorithm>

std::vector<int> nums;
nums.push_back(3);                          // O(1) amortized
nums.insert(nums.begin(), 7);               // O(n)
int first = nums[0];                        // O(1)
nums.erase(nums.begin());                   // O(n)
auto it = std::find(nums.begin(), nums.end(), 3); // O(n)
bool found = (it != nums.end());

// JavaScript Array: amortized O(1) push, O(n) unshift
const nums = [];
nums.push(3);          // O(1) amortized
nums.unshift(7);       // O(n), shifts every element right
const first = nums[0]; // O(1) random access
nums.shift();          // O(n), shifts every element left
const found = nums.includes(3); // O(n), linear scan
// V8 backs small arrays with packed C++ arrays; sparse arrays
// switch to a hash map (much slower).

// Java ArrayDeque as stack and queue: O(1) on both ends
import java.util.ArrayDeque;

ArrayDeque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2);     // O(1) amortized
int top = stack.pop();            // O(1)

ArrayDeque<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2);   // O(1)
int head = queue.poll();          // O(1)

# Python deque: O(1) at both ends
from collections import deque

stack = deque()
stack.append(1)    # O(1) push
top = stack.pop()  # O(1)

queue = deque()
queue.append(1)        # O(1) enqueue
head = queue.popleft() # O(1) dequeue
# Anti-pattern: queue = list(); queue.pop(0) is O(n).

// C++ std::stack and std::queue are adapters over std::deque
#include <stack>
#include <queue>

std::stack<int> s;
s.push(1); s.push(2);   // O(1) amortized
int top = s.top();       // O(1)
s.pop();                 // O(1)

std::queue<int> q;
q.push(1); q.push(2);    // O(1)
int head = q.front();    // O(1)
q.pop();                 // O(1)

// Java PriorityQueue (min-heap by default)
import java.util.PriorityQueue;
import java.util.Collections;

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);          // O(log n) sift-up
minHeap.offer(2);          // O(log n)
int min = minHeap.peek();   // O(1)
minHeap.poll();             // O(log n) sift-down

// Max-heap via reverse comparator
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

# Python heapq is a min-heap. For max-heap, negate keys.
import heapq

nums = [5, 2, 8, 1]
heapq.heapify(nums)        # O(n) Floyd build
heapq.heappush(nums, 3)    # O(log n)
smallest = nums[0]         # O(1) peek
heapq.heappop(nums)        # O(log n)

# Top 3 smallest
top3 = heapq.nsmallest(3, [5, 2, 8, 1, 9])  # O(n log k)

// C++ std::priority_queue is a max-heap by default
#include <queue>
#include <vector>

std::priority_queue<int> maxHeap;
maxHeap.push(5);   // O(log n)
maxHeap.push(2);   // O(log n)
int top = maxHeap.top(); // O(1)
maxHeap.pop();     // O(log n)

// Min-heap with greater<int>
#include <functional>
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

# Python Timsort: stable, O(n log n), O(n) aux
nums = [3, 1, 4, 1, 5, 9, 2, 6]
nums.sort()                      # in place, returns None
print(nums)                      # [1, 1, 2, 3, 4, 5, 6, 9]
out = sorted(nums, reverse=True) # returns new list
print(out)                       # [9, 6, 5, 4, 3, 2, 1, 1]

# Sort by key (stable preserves original order on ties)
people = [("Ada", 30), ("Bob", 25), ("Ada", 22)]
people.sort(key=lambda p: p[0])
print(people)  # Ada-30 before Ada-22 (stable)

// Java Arrays.sort: dual-pivot quicksort for primitives,
// Timsort for object arrays.
import java.util.Arrays;
import java.util.Comparator;

int[] nums = {3, 1, 4, 1, 5, 9, 2, 6};
Arrays.sort(nums);  // dual-pivot quicksort
System.out.println(Arrays.toString(nums));

Integer[] boxed = {3, 1, 4, 1, 5, 9, 2, 6};
Arrays.sort(boxed, Comparator.reverseOrder()); // Timsort, stable

// C++ std::sort: introsort, O(n log n) worst case
#include <algorithm>
#include <vector>

std::vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6};
std::sort(nums.begin(), nums.end()); // ascending
std::sort(nums.begin(), nums.end(), std::greater<int>()); // descending

// std::stable_sort preserves equal-key order, uses O(n) aux memory
std::stable_sort(nums.begin(), nums.end());

// JavaScript Array.prototype.sort: Timsort in V8 since 2019
const nums = [3, 1, 4, 1, 5, 9, 2, 6];
nums.sort((a, b) => a - b);
console.log(nums); // [1, 1, 2, 3, 4, 5, 6, 9]

// Gotcha: nums.sort() with no comparator coerces to strings:
// [10, 2, 1].sort() returns [1, 10, 2], not [1, 2, 10].

# BFS on an adjacency list: O(V + E)
from collections import deque

def bfs(graph, start):
    visited = {start}
    q = deque([start])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            if v not in visited:
                visited.add(v)
                q.append(v)
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D']

# Dijkstra with heapq: O((V + E) log V)
import heapq

def dijkstra(graph, source):
    dist = {v: float('inf') for v in graph}
    dist[source] = 0
    pq = [(0, source)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

g = {'A': [('B', 4), ('C', 1)],
     'B': [('D', 1)],
     'C': [('B', 2), ('D', 5)],
     'D': []}
print(dijkstra(g, 'A'))  # {'A': 0, 'B': 3, 'C': 1, 'D': 4}

// Java BFS with adjacency list: O(V + E)
import java.util.*;

public List<Integer> bfs(List<List<Integer>> graph, int start) {
    List<Integer> order = new ArrayList<>();
    boolean[] seen = new boolean[graph.size()];
    Deque<Integer> q = new ArrayDeque<>();
    q.offer(start);
    seen[start] = true;
    while (!q.isEmpty()) {
        int u = q.poll();
        order.add(u);
        for (int v : graph.get(u)) {
            if (!seen[v]) {
                seen[v] = true;
                q.offer(v);
            }
        }
    }
    return order;
}

// C++ Dijkstra with priority_queue: O((V + E) log V)
#include <queue>
#include <vector>
#include <limits>

std::vector<int> dijkstra(
    const std::vector<std::vector<std::pair<int,int>>>& graph, int src) {
    int n = graph.size();
    std::vector<int> dist(n, std::numeric_limits<int>::max());
    dist[src] = 0;
    std::priority_queue<std::pair<int,int>,
                        std::vector<std::pair<int,int>>,
                        std::greater<>> pq;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : graph[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

# Python recursion limit is 1000 by default
import sys
print(sys.getrecursionlimit())  # 1000
sys.setrecursionlimit(10**6)    # rare; usually rewrite iteratively

# Iterative DFS: O(V + E) time, O(V) explicit stack
def dfs_iter(graph, start):
    stack = [start]
    seen = {start}
    order = []
    while stack:
        u = stack.pop()
        order.append(u)
        for v in graph[u]:
            if v not in seen:
                seen.add(v)
                stack.append(v)
    return order

// Java has no TCO. Iterative tree traversal beats deep recursion.
import java.util.ArrayDeque;
import java.util.Deque;

void iterativeInorder(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        System.out.println(cur.val);
        cur = cur.right;
    }
}

# Union-Find with path compression and union by rank
# Amortized O(alpha(n)) per op (effectively constant)
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        # path compression
        while self.parent[x] != root:
            self.parent[x], x = root, self.parent[x]
        return root
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False
        if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1
        return True

# Trie implementation: O(L) insert and search
class TrieNode:
    __slots__ = ('children', 'is_word')
    def __init__(self):
        self.children = {}
        self.is_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):       # O(L)
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True
    def search(self, word):       # O(L)
        node = self.root
        for ch in word:
            if ch not in node.children: return False
            node = node.children[ch]
        return node.is_word
    def starts_with(self, prefix):  # O(L)
        node = self.root
        for ch in prefix:
            if ch not in node.children: return False
            node = node.children[ch]
        return True

// Java trie with array children for ASCII lowercase: faster than HashMap
class Trie {
    static class Node {
        Node[] children = new Node[26];
        boolean isWord;
    }
    Node root = new Node();

    void insert(String word) {           // O(L)
        Node cur = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (cur.children[idx] == null) cur.children[idx] = new Node();
            cur = cur.children[idx];
        }
        cur.isWord = true;
    }

    boolean search(String word) {        // O(L)
        Node n = walk(word);
        return n != null && n.isWord;
    }

    boolean startsWith(String prefix) {  // O(L)
        return walk(prefix) != null;
    }

    private Node walk(String s) {
        Node cur = root;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (cur.children[idx] == null) return null;
            cur = cur.children[idx];
        }
        return cur;
    }
}

# KMP substring search: O(n + m) time, O(m) preprocessing
def kmp_search(text, pattern):
    if not pattern: return 0
    # Build failure function
    fail = [0] * len(pattern)
    k = 0
    for i in range(1, len(pattern)):
        while k > 0 and pattern[k] != pattern[i]:
            k = fail[k - 1]
        if pattern[k] == pattern[i]:
            k += 1
        fail[i] = k
    # Search
    j = 0
    for i in range(len(text)):
        while j > 0 and pattern[j] != text[i]:
            j = fail[j - 1]
        if pattern[j] == text[i]:
            j += 1
        if j == len(pattern):
            return i - j + 1
    return -1

print(kmp_search("ABCABCABABC", "ABCAB"))  # 0

# Kahn's topological sort: O(V + E)
from collections import deque, defaultdict

def topo_sort(graph, vertices):
    in_deg = {v: 0 for v in vertices}
    for u in graph:
        for v in graph[u]:
            in_deg[v] = in_deg.get(v, 0) + 1
    q = deque([v for v in vertices if in_deg[v] == 0])
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph.get(u, []):
            in_deg[v] -= 1
            if in_deg[v] == 0:
                q.append(v)
    if len(order) != len(vertices):
        raise ValueError("cycle detected")
    return order

g = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
print(topo_sort(g, ['A', 'B', 'C', 'D']))  # ['A', 'B', 'C', 'D']

# Kruskal's MST: O(E log E)
def kruskal(n_vertices, edges):
    parent = list(range(n_vertices))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    edges.sort(key=lambda e: e[2])  # sort by weight
    mst = []
    total = 0
    for u, v, w in edges:
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            mst.append((u, v, w))
            total += w
            if len(mst) == n_vertices - 1: break
    return mst, total

# Simple Bloom filter using Python's mmh3 hash
import mmh3
from bitarray import bitarray

class BloomFilter:
    def __init__(self, size=1000, hash_count=3):
        self.size = size
        self.hash_count = hash_count
        self.bits = bitarray(size)
        self.bits.setall(0)
    def add(self, item):
        for i in range(self.hash_count):
            idx = mmh3.hash(item, i) % self.size
            self.bits[idx] = 1
    def __contains__(self, item):
        for i in range(self.hash_count):
            idx = mmh3.hash(item, i) % self.size
            if not self.bits[idx]: return False
        return True   # possibly in set; small false-positive rate

bf = BloomFilter(size=10000, hash_count=5)
bf.add("hello")
print("hello" in bf)    # True
print("world" in bf)    # almost certainly False