References

Full-text reference for every data structure and algorithm in CS Studio: complexity tables, pseudocode, and reference code.

All Data Structures (27)

• AVL Tree
• Binary Search Tree
• Bitset
• Bloom Filter
• Circular Buffer
• Circular Queue
• Deque
• Disjoint Set (Union-Find)
• Dynamic Array
• Fenwick Tree (BIT)
• Graph
• Hash Map
• Hash Set
• Heap
• LFU Cache
• Linked List
• LRU Cache
• Priority Queue
• Queue
• Red-Black Tree
• Segment Tree
• Skip List
• Sparse Matrix
• Splay Tree
• Stack
• Treap
• Trie

All Algorithms (164)

Searching

• Binary Search — O(log n)
• Binary Search (Recursive) — O(log n)
• Exponential Search — O(log n)
• Fibonacci Search — O(log n)
• Interpolation Search — O(log log n)
• Jump Search — O(√n)
• Linear Search — O(n)
• Ternary Search — O(log₃ n)

Sorting

• Bubble Sort — O(n²)
• Bucket Sort — O(n) avg
• Cocktail Shaker Sort — O(n²)
• Comb Sort — O(n²/2ᵖ)
• Counting Sort — O(n + k)
• Cycle Sort — O(n²)
• Gnome Sort — O(n²)
• Heap Sort — O(n log n)
• Insertion Sort — O(n²)
• IntroSort — O(n log n)
• Merge Sort — O(n log n)
• Odd-Even Sort — O(n²)
• Pancake Sort — O(n²)
• Pigeonhole Sort — O(n + range)
• Quick Sort — O(n log n) avg
• Radix Sort — O(d·n)
• Selection Sort — O(n²)
• Shell Sort — O(n^1.3)
• Strand Sort — O(n²) worst
• TimSort — O(n log n)
• Tree Sort — O(n log n) avg

Recursion

• Factorial — O(n)
• Fibonacci (naive) — O(2ⁿ)
• Flood Fill — O(cells)
• Generate Parentheses — O(4ⁿ/√n)
• Power (fast exponentiation) — O(log n)
• Tower of Hanoi — O(2ⁿ)

Trees

• AVL Tree Rotations — O(log n)
• Deserialise Tree — O(n)
• Diameter of Tree — O(n)
• Inorder Traversal — O(n)
• Level Order Traversal — O(n)
• Lowest Common Ancestor — O(n)
• Morris Traversal — O(n)
• Postorder Traversal — O(n)
• Preorder Traversal — O(n)
• Red-Black Tree Delete — O(log n)
• Red-Black Tree Insert — O(log n)
• Serialise Tree — O(n)
• Tree Balance Check — O(n)
• Tree Height — O(n)
• Zigzag Traversal — O(n)

Graphs

• A* Pathfinding — O(E log V)
• Articulation Points — O(V + E)
• Bellman-Ford — O(V·E)
• Bipartite Graph Check — O(V + E)
• Borůvka's Algorithm — O(E log V)
• Breadth-First Search — O(V + E)
• Bridges — O(V + E)
• Connected Components — O(V + E)
• Cycle Detection (DFS) — O(V + E)
• Depth-First Search — O(V + E)
• Dijkstra's Algorithm — O(E log V)
• Dinic's Algorithm — O(V²E)
• Edmonds-Karp — O(V · E²)
• Floyd-Warshall — O(V³)
• Ford-Fulkerson — O(E · maxFlow)
• Johnson's Algorithm — O(V·E log V)
• Kruskal's MST — O(E log E)
• Prim's MST — O(E log V)
• SCC — Kosaraju — O(V + E)
• SCC — Tarjan — O(V + E)
• Topological Sort — O(V + E)
• Topological Sort (Kahn) — O(V + E)

Dynamic Programming

• 0/1 Knapsack — O(n·W)
• Catalan Numbers — O(n²)
• Climbing Stairs — O(n)
• Coin Change — O(n·amount)
• Decode Ways — O(n)
• Edit Distance — O(n·m)
• Egg Dropping Puzzle — O(eggs · floors²)
• Fibonacci + Memoization — O(n)
• House Robber — O(n)
• Longest Common Subsequence — O(n·m)
• Longest Increasing Subsequence — O(n²)
• Longest Palindromic Subsequence — O(n²)
• Longest Palindromic Substring — O(n²)
• Matrix Chain Multiplication — O(n³)
• Maximum Subarray (Kadane) — O(n)
• Partition Equal Subset Sum — O(n·sum)
• Rod Cutting — O(n²)
• Unbounded Knapsack — O(n·capacity)
• Unique Paths — O(m·n)
• Word Break — O(n²)

Backtracking

• Combination Sum — O(2ⁿ)
• Combinations — O(C(n,k))
• Hamiltonian Cycle — O(n!)
• Knight's Tour — O(8^(n²))
• Maze Solver — O(cells)
• N-Queens — O(n!)
• Permutations — O(n!)
• Rat in a Maze — O(4^(n²))
• Subsets — O(2ⁿ)
• Sudoku Solver — O(4^cells)
• Word Search — O(R·C·4^L)

Strings

• Aho-Corasick — O(n + m + z)
• Boyer-Moore — O(n/m) best, O(nm) worst
• KMP Algorithm — O(n + m)
• Levenshtein Distance — O(n·m)
• Manacher's Algorithm — O(n)
• Naive Pattern Matching — O(n·m)
• Rabin-Karp — O(n + m) avg
• Z Algorithm — O(n + m)

Greedy

• Activity Selection — O(n log n)
• Fractional Knapsack — O(n log n)
• Gas Station — O(n)
• Huffman Coding — O(n log n)
• Interval Scheduling — O(n log n)
• Job Scheduling — O(n²) simple, O(n log n) w/ DSU
• Jump Game — O(n)
• Merge Intervals — O(n log n)
• Minimum Platforms — O(n log n)

Divide and Conquer

• Closest Pair of Points — O(n log n)
• Karatsuba Multiplication — O(n^1.585)
• Strassen Matrix Multiplication — O(n^2.807)

Two Pointers

• Container With Most Water — O(n)
• Four Sum — O(n³)
• Merge Sorted Arrays — O(n + m)
• Move Zeroes — O(n)
• Remove Duplicates — O(n)
• Three Sum — O(n²)
• Trapping Rain Water — O(n)
• Two Sum (sorted) — O(n)

Sliding Window

• Fixed Window Max Sum — O(n)
• Longest Repeating Character Replacement — O(n)
• Longest Substring w/o Repeats — O(n)
• Minimum Window Substring — O(n + m)
• Sliding Window Maximum — O(n)

Mathematics

• Binomial Coefficients — O(k)
• Euclidean GCD — O(log min)
• Extended Euclidean Algorithm — O(log min)
• Fast Modular Exponentiation — O(log n)
• Modular Inverse — O(log m)
• Pascal's Triangle — O(n²)
• Prime Factorization — O(√n)
• Sieve of Eratosthenes — O(n log log n)

Bit Manipulation

• Bit Shifting — O(1)
• Bitwise AND — O(1)
• Bitwise NOT — O(1)
• Bitwise OR — O(1)
• Bitwise XOR — O(1)
• Counting Set Bits — O(set bits)
• Gray Code — O(1) per
• Power of Two Check — O(1)
• Set / Clear / Toggle / Check — O(1)

Hashing

• Consistent Hashing — O(log n) w/ sorted ring
• Double Hashing — O(1) avg
• Linear Probing — O(1) avg
• Quadratic Probing — O(1) avg
• Separate Chaining — O(1 + α)

Algorithmic Techniques

• Binary Search on Answer — O(n log(max))
• Branch and Bound — O(2ⁿ) worst, much less in practice
• Difference Array — O(1) update, O(n) build
• Monotonic Queue — O(n)
• Monotonic Stack — O(n)
• Prefix Sum — O(n) build, O(1) query