Algorithm dossier

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

Why this snippet is Sieve of Eratosthenes

Why the sieve. A boolean table of size n+1 initialised to True. For each surviving i, mark its multiples starting from i*i as composite. The starting offset i*i is the optimisation: any smaller multiple i*k (k < i) was already crossed off by an earlier prime factor. Complexity. O(n log log n) — surprisingly close to linear because each composite is touched once per prime factor.

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.