Loading your learning space…
Loading your learning space…
Compare the costs of the implemented algorithms. This reference is free; linked All Access lessons retain their purchase requirements.
112 algorithms
| Algorithm | Best time | Average time | Worst time | Space | Properties |
|---|---|---|---|---|---|
| Big-O notationfoundations · Free lesson | O(n) | O(n) | O(n) | O(1) | — |
| Time vs space complexityfoundations · Free lesson | O(1) early duplicate | Naive O(n²); hash expected O(n) | Naive O(n²); hash expected O(n) | Naive O(1); hash O(n) | — |
| Recursion basicsfoundations · All Access lesson | O(n) | O(n) | O(n) | O(n) call stack | — |
| Recursion tree & call stackfoundations · All Access lesson | O(φⁿ) naive recurrence | O(φⁿ) | O(φⁿ) | O(n) active call stack | — |
| Master theoremfoundations · All Access lesson | Θ(n^log_b a) in case 1 | Θ(n^k log n) in case 2 | Θ(n^k) in case 3 | Depends on the algorithm | — |
| Bit manipulation basicsfoundations · All Access lesson | O(1) fixed-width operation | O(1) | O(1) | O(1) | — |
| Two pointersfoundations · All Access lesson | O(1) | O(n) | O(n) | O(1) | — |
| Sliding windowfoundations · All Access lesson | O(n) | O(n) | O(n) | O(1) auxiliary | — |
| Prefix sumsfoundations · All Access lesson | O(1) range query after preprocessing | O(1) query | O(1) query; O(n) build | O(n) | — |
| Arrays & dynamic arrayslinear · Free lesson | O(1) append | O(1) amortized append | O(n) resize | O(n) | — |
| Stringslinear · All Access lesson | O(n) code-point traversal | O(n) | O(n) | O(n) materialized code points | — |
| Singly linked listlinear · All Access lesson | O(1) with a known link | O(n) search | O(n) search | O(n) | — |
| Doubly linked listlinear · All Access lesson | O(1) with a known link | O(n) search | O(n) search | O(n) | — |
| Circular linked listlinear · All Access lesson | O(1) with a known link | O(n) search | O(n) search | O(n) | — |
| Stacklinear · Free lesson | O(1) per push/pop | O(1) per push/pop | O(1) per push/pop | O(n) | — |
| Queuelinear · All Access lesson | O(1) enqueue/dequeue | O(1) enqueue/dequeue | O(1) enqueue/dequeue | O(n) | — |
| Circular queuelinear · All Access lesson | O(1) enqueue/dequeue | O(1) enqueue/dequeue | O(1) enqueue/dequeue | O(k) capacity | — |
| Dequelinear · All Access lesson | O(1) end operation | O(1) end operation | O(1) end operation | O(n) | — |
| Monotonic stacklinear · All Access lesson | O(n) whole pass | O(n) whole pass | O(n) whole pass | O(n) | — |
| Monotonic queuelinear · All Access lesson | O(n) whole pass | O(n) whole pass | O(n) whole pass | O(k) window | — |
| Hash functionshashing · Free lesson | O(L) string hashing | O(L) | O(L) | O(1) | — |
| Hash table with chaininghashing · All Access lesson | O(1) expected key operation | O(1+α) lookup; amortized O(1) growth | O(n) collision chain or rehash | O(n+m) keys and buckets | — |
| Open addressinghashing · All Access lesson | O(1) | O(1) at suitable load | O(m) probes | O(m) | — |
| Load factor & rehashinghashing · All Access lesson | O(1) expected key operation | O(1+α) lookup; amortized O(1) growth | O(n) collision chain or rehash | O(n+m) keys and buckets | — |
| Bloom filterhashing · All Access lesson | O(1) early negative query | O(k) hash probes | O(k) | O(m) filter bits | — |
| Consistent hashinghashing · All Access lesson | O(log R) key lookup | O(log R) lookup; O(R log R) ring build | O(log R) lookup; distribution-dependent load | O(R+K) ring and teaching assignments | — |
| Binary tree & traversalstrees · Free lesson | O(n) | O(n) | O(n) | O(h) DFS stack; O(w) BFS queue | — |
| Binary search treetrees · Free lesson | O(log n) balanced operation | O(log n) for random distinct insertion order | O(n) degenerate tree | O(n) tree, O(h) recursive stack | — |
| AVL treetrees · All Access lesson | O(log n) balanced operation | O(log n) | O(log n) | O(n) tree, O(h) recursive stack | — |
| Red-black treetrees · All Access lesson | O(log n) balanced operation | O(log n) | O(log n) | O(n) tree, O(h) recursive stack | — |
| B-tree & B+ treetrees · All Access lesson | O(1) root hit | O(log_b n) page visits | O(log_b n) page visits | O(n) keys and page pointers | — |
| Heap & priority queuetrees · All Access lesson | O(1) peek | O(log n) insert/extract | O(log n) insert/extract | O(n) backing array; O(1) repair workspace | — |
| Heapifytrees · All Access lesson | O(n) build | O(n) build | O(n) build | O(n) backing array; O(1) repair workspace | — |
| Trietrees · All Access lesson | O(1) early missing edge | O(L) insert/search | O(L) | O(total stored characters) | — |
| Segment treetrees · All Access lesson | O(log n) update/query | O(log n) | O(log n) | O(n) | — |
| Fenwick treetrees · All Access lesson | O(log n) update/query | O(log n) | O(log n) | O(n) | — |
| Lowest common ancestortrees · All Access lesson | O(1) same node | O(h) | O(h) | O(n) adjacency/depth data | — |
| Tree diametertrees · All Access lesson | O(n) | O(n) | O(n) | O(n) adjacency/depth data | — |
| Bubble sortsorting · Free lesson | O(n) | O(n²) | O(n²) | O(1) | Stable · In place |
| Selection sortsorting · Free lesson | O(n²) | O(n²) | O(n²) | O(1) | Not stable · In place |
| Insertion sortsorting · Free lesson | O(n) | O(n²) | O(n²) | O(1) | Stable · In place |
| Shell sortsorting · All Access lesson | O(n log n) | gap-dependent | O(n²) | O(1) | Not stable · In place |
| Merge sortsorting · All Access lesson | O(n log n) | O(n log n) | O(n log n) | O(n) | Stable · Extra storage |
| Quick sortsorting · All Access lesson | O(n log n) | O(n log n) | O(n²) | O(log n) average; O(n) worst | Not stable · In place |
| Heap sortsorting · All Access lesson | O(n log n) | O(n log n) | O(n log n) | O(1) | Not stable · In place |
| Counting sortsorting · All Access lesson | O(n + k) | O(n + k) | O(n + k) | O(k) | Not stable · Extra storage |
| Radix sortsorting · All Access lesson | O(d(n + b)) | O(d(n + b)) | O(d(n + b)) | O(n + b) | Stable · Extra storage |
| Bucket sortsorting · All Access lesson | O(n + k) | O(n + k) for uniform input | O(n²) | O(n + k) | Stable · Extra storage |
| Tim sort overviewsorting · All Access lesson | O(n) | O(n log n) | O(n log n) | O(n) | Stable · Extra storage |
| Stability explainedsorting · All Access lesson | O(n) | O(n²) | O(n²) | O(1) auxiliary | Stable · In place |
| Sorting algorithm racesorting · All Access lesson | algorithm-dependent | Compare measured counters | Bubble O(n²), Merge O(n log n), Quick O(n²) | algorithm-dependent | — |
| Linear searchsearching · Free lesson | O(1) | O(n) | O(n) | O(1) | — |
| Binary searchsearching · Free lesson | O(1) | O(log n) | O(log n) | O(1) | — |
| Binary search on answersearching · All Access lesson | O(n) for a single-point range | O(n log S) | O(n log S) | O(1) | — |
| Lower & upper boundsearching · All Access lesson | O(log n) | O(log n) | O(log n) | O(1) | — |
| Ternary searchsearching · All Access lesson | O(1) | O(log n) | O(log n) | O(1) | — |
| Exponential searchsearching · All Access lesson | O(1) | O(log i) | O(log n) | O(1) | — |
| Interpolation searchsearching · All Access lesson | O(1) | O(log log n) for uniform keys | O(n) | O(1) | — |
| Graph representationsgraphs · Free lesson | O(V+E) adjacency list; O(V²) matrix | O(V+E) adjacency list; O(V²) matrix | O(V+E) adjacency list; O(V²) matrix | O(V+E) graph storage plus algorithm state | — |
| Breadth-first searchgraphs · Free lesson | O(V+E) | O(V+E) | O(V+E) | O(V+E) graph storage plus algorithm state | — |
| Depth-first searchgraphs · Free lesson | O(V+E) | O(V+E) | O(V+E) | O(V+E) graph storage plus algorithm state | — |
| Topological sortgraphs · All Access lesson | O(V+E) | O(V+E) | O(V+E) | O(V+E) graph storage plus algorithm state | — |
| Cycle detectiongraphs · All Access lesson | O(V+E) | O(V+E) | O(V+E) | O(V+E) graph storage plus algorithm state | — |
| Connected componentsgraphs · All Access lesson | O(V+E) | O(V+E) | O(V+E) | O(V+E) graph storage plus algorithm state | — |
| Union-Findgraphs · All Access lesson | O((V+E) α(V)) amortized | O((V+E) α(V)) amortized | O((V+E) α(V)) amortized | O(V+E) graph storage plus algorithm state | — |
| Dijkstragraphs · All Access lesson | O((V+E) log(V+E)) with lazy heap entries | O((V+E) log(V+E)) with lazy heap entries | O((V+E) log(V+E)) with lazy heap entries | O(V+E) graph storage plus algorithm state | — |
| Bellman-Fordgraphs · All Access lesson | O(VE) | O(VE) | O(VE) | O(V+E) graph storage plus algorithm state | — |
| Floyd-Warshallgraphs · All Access lesson | O(V³) time; O(V²) distance workspace | O(V³) time; O(V²) distance workspace | O(V³) time; O(V²) distance workspace | O(V+E) graph storage plus algorithm state | — |
| A-star searchgraphs · All Access lesson | O((V+E) log(V+E)) with lazy heap entries | O((V+E) log(V+E)) with lazy heap entries | O((V+E) log(V+E)) with lazy heap entries | O(V+E) graph storage plus algorithm state | — |
| Prim MSTgraphs · All Access lesson | O((V+E) log(V+E)) | O((V+E) log(V+E)) | O((V+E) log(V+E)) | O(V+E) graph storage plus algorithm state | — |
| Kruskal MSTgraphs · All Access lesson | O(E log E) | O(E log E) | O(E log E) | O(V+E) graph storage plus algorithm state | — |
| Strongly connected componentsgraphs · All Access lesson | O(V+E) | O(V+E) | O(V+E) | O(V+E) graph storage plus algorithm state | — |
| Bipartite checkgraphs · All Access lesson | O(V+E) | O(V+E) | O(V+E) | O(V+E) graph storage plus algorithm state | — |
| Bridges & articulation pointsgraphs · All Access lesson | O(V+E) | O(V+E) | O(V+E) | O(V+E) graph storage plus algorithm state | — |
| Max flowgraphs · All Access lesson | O(VE²) Edmonds–Karp | O(VE²) Edmonds–Karp | O(VE²) Edmonds–Karp | O(V+E) graph storage plus algorithm state | — |
| Greedy algorithmsparadigms · Free lesson | O(n log n) | O(n log n) | O(n log n) | O(n) sorted/indexed teaching copy | — |
| Divide & conquerparadigms · Free lesson | O(n log n) | O(n log n) | O(n log n) | O(log n) recursion stack | — |
| Backtrackingparadigms · Free lesson | Search/output dependent | Constraint and pruning dependent | Queens O(n!·n) simple safety checks; subsets O(n·2ⁿ); permutations O(n·n!); Sudoku exponential in blanks | O(depth) search state plus stored output | — |
| Dynamic programming introparadigms · All Access lesson | O(n) | O(n) | O(n) | O(n) trace table; O(1) rolling-value alternative | — |
| Fibonacci DPparadigms · All Access lesson | O(1) for a base case | O(n) arithmetic additions | O(n) arithmetic additions | O(n) displayed table; O(1) rolling-value alternative | — |
| 0-1 Knapsackparadigms · All Access lesson | O(nW) | O(nW) | O(nW) pseudo-polynomial | O(nW) table; O(W) value-only optimization | — |
| Longest common subsequenceparadigms · All Access lesson | O(mn) | O(mn) | O(mn) | O(mn) reconstruction table | — |
| Longest increasing subsequenceparadigms · All Access lesson | O(n log n) | O(n log n) | O(n log n) | O(n) | — |
| Edit distanceparadigms · All Access lesson | O(mn) | O(mn) | O(mn) | O(mn) reconstruction table | — |
| Coin changeparadigms · All Access lesson | O(kA) | O(kA) | O(kA) | O(A) | — |
| Matrix chain multiplicationparadigms · All Access lesson | O(n³) | O(n³) | O(n³) | O(n²) | — |
| DP on gridsparadigms · All Access lesson | O(RC) | O(RC) | O(RC) | O(RC) displayed/reconstruction table | — |
| DP on treesparadigms · All Access lesson | O(n) | O(n) | O(n) | O(n) | — |
| Naive string matchingstrings · Free lesson | O(n) | O(nm) | O(nm) | O(1) auxiliary, excluding output | — |
| KMPstrings · All Access lesson | O(n+m) | O(n+m) | O(n+m) | O(m) | — |
| Rabin-Karpstrings · All Access lesson | O(n+m) expected | O(n+m) expected | O(nm) | O(1) auxiliary, excluding output | — |
| Z-algorithmstrings · All Access lesson | O(n+m) | O(n+m) | O(n+m) | O(n+m) | — |
| Manacher overviewstrings · All Access lesson | O(n) | O(n) | O(n) | O(n) | — |
| Huffman codingstrings · All Access lesson | O(n+σ log σ) | O(n+σ log σ) | O(n+σ log σ) | O(σ) tree/codebook plus encoded output | — |
| Run-length encodingstrings · All Access lesson | O(n) | O(n) | O(n) | O(r) output runs; O(1) working state | — |
| Euclidean GCDmath · Free lesson | O(1) | O(log min(a,b)) | O(log min(a,b)) | O(1) | — |
| Sieve of Eratosthenesmath · Free lesson | O(n log log n) | O(n log log n) | O(n log log n) | O(n) | — |
| Primality testmath · All Access lesson | O(1) | O(√n) upper bound | O(√n) | O(1) | — |
| Fast exponentiationmath · All Access lesson | O(1) for exponent zero | O(log exponent) multiplications | O(log exponent) multiplications | O(1) integer variables; output-sized bits | — |
| Tower of Hanoimath · All Access lesson | Θ(2ⁿ) for n disks | Θ(2ⁿ) | Θ(2ⁿ) | O(n) recursion stack | — |
| Reservoir samplingmath · All Access lesson | O(n) | O(n) | O(n) | O(k) | — |
| K-means clusteringmath · All Access lesson | O(I·n·k·d) | O(I·n·k·d) | O(I·n·k·d) for I capped iterations | O(n+k) in two dimensions | — |
| PageRankmath · All Access lesson | O(I(V+E)) | O(I(V+E)) | O(I(V+E)) | O(V+E) | — |
| LRU cachemath · All Access lesson | O(1) expected access | O(1) expected access | O(1) policy-link updates; hash-dependent lookup | O(k) cache capacity | — |
| LFU cachemath · All Access lesson | O(1) expected access | O(1) expected access | O(1) policy-link updates; hash-dependent lookup | O(k) cache capacity | — |
| Cryptographic hash functionssecurity · Free lesson | O(n) input hashing | O(n) | O(n) | O(1) digest/state, excluding input buffers | — |
| Symmetric encryptionsecurity · All Access lesson | O(n) encryption/decryption | O(n) | O(n) | O(n) returned ciphertext/plaintext | — |
| Public-key cryptographysecurity · All Access lesson | O(log exponent) modular multiplications | O(log exponent) multiplications | O(log exponent) multiplications | O(1) arithmetic words in this bounded toy | — |
| Diffie-Hellman key exchangesecurity · All Access lesson | O(log private exponent) modular multiplications | O(log exponent) | O(log exponent) | O(1) bounded toy arithmetic | — |
| Digital signaturessecurity · All Access lesson | O(n) message processing plus fixed-parameter curve operations | O(n) message processing | O(n) message processing | O(n) message buffers plus fixed-size signature/key data | — |
| Digital certificates & TLSsecurity · All Access lesson | O(k) chain checks plus signature verification | O(k) chain length checks | O(k) checks in this fixed-chain model | O(k) parsed certificates | — |
| Password hashing & saltingsecurity · All Access lesson | O(Nrp) KDF work | O(Nrp) | O(Nrp) | O(Nr) memory | — |
These are operation-count bounds under each lesson’s stated model, not CPU benchmarks. Output storage, arithmetic bit costs and distribution assumptions can change the relevant bound; open the lesson for its assumptions.