Algorithm dossier

  • Category: Hashing
  • Worst-case complexity: O(n)
  • Approach: Divide & conquer
  • Data structure: Array
  • First formalised: 1960s

Why this snippet is Quickselect

Why quickselect. Same partition machinery as quicksort, but you only recurse into the side containing index k — never both. That's the magic: O(n) average instead of O(n log n), because the recurrence becomes T(n) = T(n/2) + O(n) which sums to 2n. Worst case. O(n²) with adversarial pivots, same as quicksort. Median-of-medians fixes this for a guaranteed-linear variant.

How to read a redacted algorithm

Algodle strips identifier names so the snippet has to be read for its shape: the control flow, the data structures it manipulates, the order in which it visits its input. Loops with two pointers crawling toward each other are usually search or partition. A recursion that splits its input in half and recurses on both halves is divide-and-conquer. A priority queue plus graph traversal is almost certainly Dijkstra, Prim, or A*. Six hint columns — category, complexity, approach, data structure, era — let you triangulate even when the snippet itself is opaque.