Algorithm dossier

  • Category: DP
  • Worst-case complexity: O(n)
  • Approach: Recursive
  • Data structure: Hash table
  • First formalised: 1950s

Why this snippet is Memoized Fibonacci

Why memoized Fibonacci. The recurrence fib(n) = fib(n-1) + fib(n-2) is the classic; what makes this *fast* is the m dict — every sub-problem is computed at most once. Without memoization the same recursion is O(2ⁿ). Teaching point. This is canonical DP: overlapping sub-problems + optimal substructure. The dict-as-cache pattern is the simplest top-down DP shape.

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.