Problem. Counting how many entries in a word list start with a given prefix, the kind of lookup behind autocomplete or a spell checker, when the list has to be checked again for every keystroke. Baseline complexity. Testing every word against the prefix costs O(n) calls in the number of words, and each call itself does up to O(L) character comparisons for a prefix of length L, so a full pass over an n-word dictionary is O(n x L) in the worst case. Solution. A trie stores the dictionary as a tree of shared characters, so a prefix query becomes a walk of L pointer hops from the root, with no dependency on how many words the dictionary holds. Measured result. On a Raspberry Pi running CPython 3.13.5, the executed comparison found the trie about 62 times faster than the linear scan at 500 words and about 3,210 times faster at 16,000 words, while using roughly 11 times more memory than the same words held fresh in a list.
Reproduce the result
Complete code
"""Benchmark: linear-scan prefix counting vs a trie (prefix tree) in Python.Correctness is checked against the same linear-scan baseline used for timing,across many random prefixes, including prefixes that do not appear in thedictionary at all. Only after every trial agrees does the script move on tomeasuring wall-clock time with timeit, using Timer.repeat() and reporting theminimum sample as the Python documentation recommends, plus peak memory withtracemalloc."""from __future__ import annotationsimport jsonimport platformimport randomimport sysimport timeitimport tracemallocCONSONANTS = "bcdfghjklmnprstvw"VOWELS = "aeiou"def build_syllables(rng: random.Random, count: int = 40) -> list[str]: """Deterministic syllable pool (consonant+vowel). Composing words from a shared syllable pool produces realistic overlapping prefixes, closer to a real word list than uniform-random character strings would give.""" syllables: set[str] = set() while len(syllables) < count: syllables.add(rng.choice(CONSONANTS) + rng.choice(VOWELS)) return sorted(syllables)def build_dictionary(n: int, seed: int) -> list[str]: rng = random.Random(seed) syllables = build_syllables(rng) words: set[str] = set() while len(words) < n: length = rng.randint(2, 4) words.add("".join(rng.choice(syllables) for _ in range(length))) return sorted(words)def baseline_count_prefix(words: list[str], prefix: str) -> int: """O(n) per query: check every word directly.""" return sum(1 for w in words if w.startswith(prefix))class TrieNode: """No __slots__: this is deliberately the exact same shape as the TrieNode shown in the article body, so the memory measurement below matches what a reader gets by copying the article's own code, not a separately optimised internal version.""" def __init__(self) -> None: self.children: dict[str, "TrieNode"] = {} self.count = 0class Trie: """Each node's count is the number of inserted words that pass through it, so a prefix query is a count read at the end of a pointer walk.""" def __init__(self) -> None: self.root = TrieNode() def insert(self, word: str) -> None: node = self.root node.count += 1 for ch in word: child = node.children.get(ch) if child is None: child = TrieNode() node.children[ch] = child node = child node.count += 1 def count_prefix(self, prefix: str) -> int: """O(len(prefix)) per query: one child-pointer hop per character.""" node = self.root for ch in prefix: node = node.children.get(ch) if node is None: return 0 return node.countdef make_queries(words: list[str], rng: random.Random, n_queries: int) -> list[str]: """Half the queries are real prefixes of dictionary words (a random-length cut of a random word), half use a disjoint alphabet so they almost never match, so neither implementation is timed on an unrealistically easy or hard workload alone.""" queries: list[str] = [] for _ in range(n_queries // 2): word = rng.choice(words) cut = rng.randint(1, len(word)) queries.append(word[:cut]) for _ in range(n_queries - len(queries)): length = rng.randint(1, 4) queries.append("".join(rng.choice("xzqj") for _ in range(length))) rng.shuffle(queries) return queriesdef run_correctness_checks(seed: int, trials: int = 300) -> dict: rng = random.Random(seed) words = build_dictionary(500, seed=seed) trie = Trie() for w in words: trie.insert(w) queries = make_queries(words, rng, trials) mismatches = [] for q in queries: expected = baseline_count_prefix(words, q) got = trie.count_prefix(q) if expected != got: mismatches.append({"prefix": q, "expected": expected, "got": got}) return {"trials": trials, "seed": seed, "mismatches": mismatches, "all_agree": len(mismatches) == 0}def main() -> None: seed = 20260925 correctness = run_correctness_checks(seed=seed) if not correctness["all_agree"]: print(json.dumps({"error": "correctness_check_failed", "detail": correctness}, indent=2)) sys.exit(1) sizes = [500, 1000, 2000, 4000, 8000, 16000] n_queries = 200 repeat = 5 results = [] for n in sizes: words = build_dictionary(n, seed=seed + n) rng = random.Random(seed + n + 1) queries = make_queries(words, rng, n_queries) trie = Trie() build_start = timeit.default_timer() for w in words: trie.insert(w) build_time = timeit.default_timer() - build_start # Sanity: both implementations must agree on this size's own queries too. for q in queries[:20]: assert baseline_count_prefix(words, q) == trie.count_prefix(q) def run_baseline(words=words, queries=queries): for q in queries: baseline_count_prefix(words, q) def run_trie(trie=trie, queries=queries): for q in queries: trie.count_prefix(q) baseline_times = timeit.repeat(run_baseline, repeat=repeat, number=1) trie_times = timeit.repeat(run_trie, repeat=repeat, number=1) baseline_best = min(baseline_times) trie_best = min(trie_times) results.append({ "n": n, "n_queries": n_queries, "baseline_seconds_total": baseline_best, "trie_seconds_total": trie_best, "baseline_seconds_per_query": baseline_best / n_queries, "trie_seconds_per_query": trie_best / n_queries, "speedup": baseline_best / trie_best if trie_best > 0 else None, "trie_build_seconds": build_time, "baseline_all_samples": baseline_times, "trie_all_samples": trie_times, }) # Memory: peak traced allocation for holding the same n words fresh in a # plain list versus inserted fresh into a trie. Both structures allocate # their string content *inside* the tracemalloc window via a forced copy # (''.join(w) builds a new string object rather than aliasing the # original, confirmed below with an `is not` check), so the comparison # is a fair "materialise these words in structure X from scratch" cost, # not a comparison against strings that already existed before tracing # started. mem_n = sizes[-1] mem_words = build_dictionary(mem_n, seed=seed + mem_n + 999) tracemalloc.start() baseline_list = [''.join(w) for w in mem_words] assert all(a is not b for a, b in zip(baseline_list, mem_words)), "baseline strings must be fresh allocations, not aliases" _, baseline_peak = tracemalloc.get_traced_memory() tracemalloc.stop() del baseline_list tracemalloc.start() mem_trie = Trie() for w in mem_words: mem_trie.insert(''.join(w)) _, trie_peak = tracemalloc.get_traced_memory() tracemalloc.stop() output = { "correctness": { "trials": correctness["trials"], "seed": correctness["seed"], "all_agree": correctness["all_agree"], }, "timing_methodology": { "repeat": repeat, "n_queries": n_queries, "reported_value": "min(timeit.repeat(..., number=1)) over the full query batch, per Python timeit documentation", }, "memory_methodology": { "n": mem_n, "tool": "tracemalloc.get_traced_memory(), peak bytes, one tracemalloc session per structure", "baseline_peak_bytes": baseline_peak, "trie_peak_bytes": trie_peak, "trie_overhead_ratio": trie_peak / baseline_peak if baseline_peak else None, }, "python_version": sys.version, "platform": platform.platform(), "processor": platform.processor() or platform.machine(), "results": results, } print(json.dumps(output, indent=2))if __name__ == "__main__": main()
Output
{ "correctness": { "trials": 300, "seed": 20260925, "all_agree": true }, "timing_methodology": { "repeat": 5, "n_queries": 200, "reported_value": "min(timeit.repeat(..., number=1)) over the full query batch, per Python timeit documentation" }, "memory_methodology": { "n": 16000, "tool": "tracemalloc.get_traced_memory(), peak bytes, one tracemalloc session per structure", "baseline_peak_bytes": 900912, "trie_peak_bytes": 9778119, "trie_overhead_ratio": 10.853578373914434 }, "python_version": "3.13.5 (main, Jul 15 2026, 20:25:40) [GCC 14.2.0]", "platform": "Linux-6.12.47+rpt-rpi-v8-aarch64-with-glibc2.41", "processor": "aarch64", "results": [ { "n": 500, "n_queries": 200, "baseline_seconds_total": 0.007371874991804361, "trie_seconds_total": 0.00011899881064891815, "baseline_seconds_per_query": 3.6859374959021806e-05, "trie_seconds_per_query": 5.949940532445908e-07, "speedup": 61.94914849656425, "trie_build_seconds": 0.0020200968720018864, "baseline_all_samples": [ 0.007515002973377705, 0.010388538707047701, 0.007452280726283789, 0.007371874991804361, 0.00819005398079753 ], "trie_all_samples": [ 0.00018783193081617355, 0.00011931406334042549, 0.00011899881064891815, 0.00015883194282650948, 0.00012057321146130562 ] }, { "n": 1000, "n_queries": 200, "baseline_seconds_total": 0.015401873737573624, "trie_seconds_total": 0.00012322096154093742, "baseline_seconds_per_query": 7.700936868786811e-05, "trie_seconds_per_query": 6.161048077046871e-07, "speedup": 124.99394214235777, "trie_build_seconds": 0.014341900125145912, "baseline_all_samples": [ 0.016068813391029835, 0.015476189088076353, 0.015404521953314543, 0.015683594159781933, 0.015401873737573624 ], "trie_all_samples": [ 0.00019286898896098137, 0.0001259986311197281, 0.0001278882846236229, 0.00012740585952997208, 0.00012322096154093742 ] }, { "n": 2000, "n_queries": 200, "baseline_seconds_total": 0.03157900180667639, "trie_seconds_total": 0.00011866632848978043, "baseline_seconds_per_query": 0.00015789500903338194, "trie_seconds_per_query": 5.933316424489022e-07, "speedup": 266.1159421427282, "trie_build_seconds": 0.010003504808992147, "baseline_all_samples": [ 0.05019837198778987, 0.05714163836091757, 0.03506325464695692, 0.03157900180667639, 0.032003480941057205 ], "trie_all_samples": [ 0.0001988871954381466, 0.00011946214362978935, 0.00011879485100507736, 0.00011983281001448631, 0.00011866632848978043 ] }, { "n": 4000, "n_queries": 200, "baseline_seconds_total": 0.06328911427408457, "trie_seconds_total": 0.00012327730655670166, "baseline_seconds_per_query": 0.0003164455713704228, "trie_seconds_per_query": 6.163865327835083e-07, "speedup": 513.3881980539103, "trie_build_seconds": 0.028949928004294634, "baseline_all_samples": [ 0.0647673080675304, 0.0650761746801436, 0.06367322197183967, 0.0633604465983808, 0.06328911427408457 ], "trie_all_samples": [ 0.0002239062450826168, 0.00012579606845974922, 0.00012492528185248375, 0.00012327730655670166, 0.00012379512190818787 ] }, { "n": 8000, "n_queries": 200, "baseline_seconds_total": 0.13085877196863294, "trie_seconds_total": 0.00012125913053750992, "baseline_seconds_per_query": 0.0006542938598431647, "trie_seconds_per_query": 6.062956526875496e-07, "speedup": 1079.1663389682108, "trie_build_seconds": 0.05405040085315704, "baseline_all_samples": [ 0.13631423376500607, 0.13326288480311632, 0.13499992759898305, 0.13085877196863294, 0.15643913112580776 ], "trie_all_samples": [ 0.00022777728736400604, 0.00012344308197498322, 0.00012153619900345802, 0.00012125913053750992, 0.00012159207835793495 ] }, { "n": 16000, "n_queries": 200, "baseline_seconds_total": 0.4098286950029433, "trie_seconds_total": 0.0001276656985282898, "baseline_seconds_per_query": 0.0020491434750147166, "trie_seconds_per_query": 6.38328492641449e-07, "speedup": 3210.170779836592, "trie_build_seconds": 0.09690684266388416, "baseline_all_samples": [ 0.4210807466879487, 0.4109025211073458, 0.4098286950029433, 0.4146644198335707, 0.6274139718152583 ], "trie_all_samples": [ 0.000256925355643034, 0.00013429485261440277, 0.0001276656985282898, 0.00012772204354405403, 0.000131258275359869 ] } ]}
Environment
CPython 3.13.5 on Linux 6.12.47+rpt-rpi-v8 (aarch64), a Raspberry Pi. No third-party packages: the benchmark uses only the standard library timeit and tracemalloc modules.[2][3]
Methodology
Dictionaries of six sizes (500 to 16,000 words) were built from a fixed pool of 40 two-character syllables combined into two-to-four-syllable words, so that words genuinely share prefixes the way a real word list does, rather than being independent random strings that rarely overlap. For each size, 200 queries were built: half are random-length cuts of a real word already in that dictionary, half are short strings drawn from a disjoint four-letter alphabet that almost never appears as a prefix, so neither implementation is timed only on its easy case. Before any timing ran, the trie’s prefix count was checked against the direct linear scan across 300 queries built the same way, plus a further 20-query spot check at every benchmarked size. Timing used timeit.repeat() with repeat=5 and the full 200-query batch as the timed statement, and each reported figure is min(samples), which is what the Python documentation recommends over an average.[2] Reported multipliers are order-of-magnitude figures from a single run on a shared, non-isolated machine, not averages across repeated runs; a second full run of the same script produced speedups in the same rising order but individual ratios varying by roughly a quarter at some sizes, consistent with the timing variance the Python documentation itself warns about. Peak memory was measured with tracemalloc.get_traced_memory(), building each structure’s word strings with a fresh ''.join() copy inside the tracing window rather than reusing strings that already existed beforehand, so both the list and the trie pay for their own string allocations rather than the list baseline silently getting them for free; each structure used its own tracing session so neither measurement includes the other’s allocations.[3]
The problem
An autocomplete box, a spell checker, or an IP routing table all ask a version of the same question repeatedly: given a prefix, which stored entries share it, or how many are there. The direct way to answer is to hold the entries in a list and check each one with str.startswith(). That works, and for a short list or a one-off query it is the right amount of code to write. It stops being the right approach the moment the same dictionary gets queried on every keystroke, because each query re-examines the entire list regardless of how much of the previous query’s work could have been reused.
Most of that re-examination is genuinely wasted. If a user has typed “te” and then adds an “n” to make “ten”, every word that failed to match “te” also cannot match “ten”, so re-checking them is pure repetition. A data structure that already groups words by their shared prefixes never repeats that check.
Baseline complexity
The baseline in the benchmark is a direct translation of that first instinct:
def baseline_count_prefix(words, prefix): return sum(1 for w in words if w.startswith(prefix))
For each of the n words, str.startswith() compares up to L characters, where L is the prefix length, so a single query costs up to O(n x L) character comparisons in the worst case, when most words share a long run of the prefix before diverging. In practice CPython’s startswith() can return without comparing every character of a non-matching word: it is not obliged to run a full L-character comparison on every candidate, so a query against words that mostly do not share the prefix can behave closer to O(n) than O(n x L). Either way, the cost scales with the size of the dictionary, and every one of the 200 queries in the benchmark repeats that full pass from scratch.
The solution
A trie (a name Edward Fredkin coined in 1960 from the middle syllable of “retrieval”) stores the dictionary as a tree in which each edge is one character and each node represents a shared prefix.[1] Wikipedia’s own account of the structure credits three originators rather than one: Axel Thue first described the underlying idea abstractly in 1912, decades before it reached a computer; René de la Briandais then described it in a computer context in 1959; and Fredkin’s independent 1960 description is the one that gave the structure its name.[1] Inserting a word walks from the root one character at a time, creating a child node when a branch does not exist yet, and increments a counter at every node the walk touches:
class TrieNode: def __init__(self): self.children = {} self.count = 0def insert(self, word): node = self.root node.count += 1 for ch in word: child = node.children.get(ch) if child is None: child = TrieNode() node.children[ch] = child node = child node.count += 1
Because every word that shares a prefix passes through the same node on its way into the tree, that node’s counter already holds the answer to “how many words have this prefix” by the time insertion finishes. A query just walks the same path without inserting anything:
def count_prefix(self, prefix): node = self.root for ch in prefix: node = node.children.get(ch) if node is None: return 0 return node.count
The walk takes exactly L steps, one child-pointer hop per character in the prefix, and each hop is a single dictionary lookup. Unlike the linear scan, this cost does not grow with how many words are stored. Wikipedia’s structural summary makes the same point about what a trie node actually holds: nodes do not store their own key directly, only a position in the tree that a path of characters defines, which is what lets one node’s count summarise every word that passes through it.[1]
What the measurement shows
Correctness came first: 300 randomly built queries were checked against the direct linear scan before any timing began, all in agreement, and each of the six benchmarked sizes ran a further 20-query spot check as a guard against a size-dependent bug the smaller correctness run might miss. That rules out a fast-but-wrong trie skewing the comparison.
The timed results widen exactly as the complexity argument predicts. At 500 words, the linear scan averaged about 36.9 microseconds per query against about 0.60 microseconds for the trie, a ratio near 62x. At 16,000 words, the linear scan had grown to about 2,049 microseconds per query while the trie stayed at about 0.64 microseconds, a ratio near 3,210x. The trie’s own per-query time grew only about 7% across a 32-fold increase in dictionary size (from 500 to 16,000 words), consistent with a query cost that depends on prefix length rather than dictionary size; the linear scan’s time, by contrast, grew roughly in step with the word count, consistent with its O(n) dependency. These ratios and the growth percentage above come from a single timed run on a shared, non-isolated machine: repeated full runs of the same script produced speedups in the same rising order but individual figures shifting by roughly a quarter at some sizes, and the per-query growth percentage itself is unstable across runs too, so treat any single multiplier or percentage quoted here as an order-of-magnitude figure rather than a precise constant.
Building the trie is not free. Inserting all 16,000 words took about 96.9 milliseconds in this run, work the linear-scan baseline never has to do because it needs no preprocessing. That cost is paid once and amortised across every later query, so it matters most when the dictionary is queried many times relative to how often it changes.
Where it stops helping
The clearest cost is memory. With 16,000 words, a plain Python list built by allocating each word fresh peaked at about 880 KiB of traced allocations, while a trie built from the same words, using the exact TrieNode shown above, peaked at about 9.3 MiB, roughly 11 times more. The TrieNode shown deliberately omits __slots__ for readability; adding it back (not shown in the code above, a one-line change: __slots__ = ("children", "count") as the class’s first line), a standard Python idiom for a class with a small, fixed set of attributes, brings the ratio down to roughly 9 times instead of 11, so a reader building a memory-conscious version of this structure has a smaller, cheaper option than jumping straight to a radix tree. That is the practical version of a limitation the trie’s own literature already documents: a straightforward trie implementation, with one dictionary of children per node, is memory-heavy compared with just storing the strings, which is why production systems that care about memory often reach for a compressed variant such as a radix tree instead.[1] Wikipedia’s own account of tries also notes they are less efficient than a hash table once the data lives on a secondary storage device with high random-access latency, a caveat this in-memory benchmark did not test and is not positioned to speak to.[1] This benchmark did not build or measure a radix tree, so the size of that gap for this workload is not something this article can report; nor did it measure a sorted-list alternative using the standard library’s bisect module, whose own documentation notes it is effective for searching ranges of values though dictionaries are more performant for locating specific ones, or a specialised cache-aware structure such as a HAT-trie, which peer-reviewed benchmarking cited on its own Wikipedia page found considerably faster than other sorted access methods for exactly this kind of string-dictionary workload.[4][5]
The other limit is workload shape. The trie’s advantage comes entirely from shared prefixes; a dictionary built from genuinely independent random strings, with almost no character overlap between entries, would give the linear scan less to lose and the trie less structure to exploit, though this benchmark did not construct that case separately to measure it. The structure also answers exactly one question well: how many, or which, stored entries share a given prefix. It is not a general-purpose associative container, and looking up a single exact word by equality gains nothing over a plain Python set, which does that in O(1) average time with far less memory overhead than a character-by-character tree.
Sources
[2] timeit — Measure execution time of small code snippets
[3] tracemalloc — Trace memory allocations
