Algorithm dossier

  • Category: Math
  • Worst-case complexity: O(log n)
  • Approach: Iterative
  • Data structure: No DS
  • First formalised: 1900s

Why this snippet is Euclidean GCD

Why Euclid. The recurrence gcd(a, b) = gcd(b, a mod b) and the base case gcd(a, 0) = a. The simultaneous assignment a, b = b, a % b is the iterative version — replace a with b and b with the remainder. Why it's so fast. O(log min(a, b)) — the worst case is consecutive Fibonacci numbers; for any other input it converges faster. One of the oldest non-trivial algorithms, recorded ~300 BCE.

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.