Time Complexity — O(m) Where m Is String Length

Throughout the previous pages, we've stated that trie operations run in O(m) time, where m is the length of the string being inserted, searched, or prefix-checked. Now it's time to rigorously verify this claim, understand its implications, and appreciate why this bound is so powerful.

The key insight isn't just that operations are O(m)—it's that the time is independent of n, the number of strings in the trie. Whether your trie contains 100 words or 100 million words, inserting, searching, or checking a prefix for a 10-character string takes the same time.

This independence from n is what makes tries exceptional for large-scale string processing. In this page, we'll formally analyze each operation, compare tries to alternative data structures, and identify the conditions under which the O(m) bound holds.

Let's rigorously analyze the time complexity of the insert operation.

Operation Definition

Insert(word): Add word to the trie, creating any necessary nodes.

Algorithm Breakdown

function insert(word):
    current = root
    for each character c in word:        // Loop runs m times
        if c not in current.children:    // O(1) lookup
            create new node              // O(1)
            current.children[c] = node   // O(1)
        current = current.children[c]    // O(1)
    current.isEndOfWord = true           // O(1)

Time Analysis

Loop iterations: Exactly m (the length of the word).

Work per iteration:

1. Child lookup: O(1)

   • Array-based: children[index] is direct array access
   • Hash map-based: children.has(c) is amortized O(1) hash lookup

2. Node creation (if needed): O(1)

   • Allocating a new TrieNode object
   • Array-based node: initialize array of size Σ (alphabet size)
   • Hash map-based node: initialize empty Map

3. Pointer update: O(1)

Total time: O(m × 1) = O(m)

Space Analysis for Insert

New space per insert:

• Best case: O(1) — the entire word is already a prefix of an existing word; only set isEndOfWord
• Worst case: O(m × Σ) for array-based, O(m) for hash map-based — create m new nodes

Average case: Depends on prefix overlap in the dictionary. More shared prefixes = less new space per word.

Operation Definition

Search(word): Return true if word was previously inserted, false otherwise.

Algorithm Breakdown

function search(word):
    current = root
    for each character c in word:        // Loop runs at most m times
        if c not in current.children:    // O(1) lookup
            return false                 // Early exit
        current = current.children[c]    // O(1)
    return current.isEndOfWord           // O(1)

Time Analysis

Loop iterations: At most m (may exit early if path breaks).

Work per iteration:

1. Child lookup: O(1)
2. Pointer update: O(1)

Final isEndOfWord check: O(1)

Total time: O(m × 1 + 1) = O(m)

Best, Worst, and Average Cases

Best case: O(1)

• The first character doesn't exist in the trie
• Example: search("xyz") in a trie containing only words starting with "a"

Worst case: O(m)

• The entire path exists (whether or not it's a word)
• We must check every character before returning

Average case: O(m) or less

• Depends on prefix distribution
• Common prefixes exist → walk further before potential failure
• Random queries often fail early

Space Analysis for Search

Auxiliary space: O(1)

• Only need a pointer to walk the trie
• No new allocations

Search is a purely read-only operation that doesn't modify the trie.

Operation Definition

StartsWith(prefix): Return true if any word in the trie starts with prefix.

Algorithm Breakdown

function startsWith(prefix):
    current = root
    for each character c in prefix:      // Loop runs at most m times
        if c not in current.children:    // O(1) lookup
            return false                 // Early exit
        current = current.children[c]    // O(1)
    return true                          // Path exists

Time Analysis

Identical to search, minus the isEndOfWord check:

Total time: O(m) where m is the prefix length

Comparison: StartsWith vs Search

Algorithmically, startsWith is simpler:

• Same loop structure
• Same early exit on missing child
• No final isEndOfWord check (O(1) difference, asymptotically irrelevant)

Both are O(m). The semantic difference is profound; the complexity difference is negligible.

The O(m) complexity has a remarkable property: it is independent of n (the number of strings in the trie).

Why This Independence Matters

Consider two scenarios:

1. Small dictionary: 1,000 words
2. Large dictionary: 1,000,000 words

For a 10-character query:

• Search in small dictionary: O(10) = 10 operations
• Search in large dictionary: O(10) = 10 operations

The trie doesn't slow down as it grows. This is fundamentally different from most search data structures.

The One Caveat: Alphabet Size

While O(m) is independent of n, it hides a dependency on alphabet size Σ in the constant factors:

Array-based tries:

• Child lookup: O(1) with constant factor 1 (array indexing)
• Node creation: O(Σ) to initialize array (often optimized with lazy initialization)
• Memory per node: O(Σ) pointers

Hash map-based tries:

• Child lookup: O(1) average, but with hash computation overhead
• Node creation: O(1)
• Memory per node: O(actual children)

For fixed, small alphabets (lowercase English, ASCII), this is a non-issue. For Unicode or very large character sets, the constant factors become significant.

When m Matters More Than You Think

Although O(m) sounds efficient, consider:

1. Very long strings: For m = 1000 characters, every operation touches 1000 nodes. For databases of URLs, filepaths, or DNA sequences, m can be large.

2. Many short queries: For autocomplete with single-character typing, m = 1 is tiny, and the constant overhead of function calls may dominate.

3. Combined with other operations: Building a trie from n strings of average length L takes O(n × L) total time.

Let's rigorously compare trie complexity against other string-storing data structures. We'll use:

• n = number of strings in the collection
• m = length of the query/insert string
• L = average length of strings in the collection

Insert Operation Comparison

Analysis:

• Tries and hash sets tie for insert: both O(m)
• BSTs are O(m log n) because each comparison is O(m) and there are O(log n) comparisons
• Unsorted arrays are O(m) but searches become O(n × m)

Exact Search Comparison

Analysis:

• Tries and hash sets are equivalent for exact search
• This is why the real advantage of tries lies elsewhere (prefix operations)

Prefix Search Comparison (The Trie's Strength)

The Balanced View

When hash sets are better:

• Only exact lookups needed (no prefix queries)
• Memory is constrained (tries can use more memory)
• Strings have little prefix overlap

When tries are better:

• Prefix queries are frequent (autocomplete, routing)
• Many strings share prefixes (dictionary words, URLs)
• Sorted enumeration is needed (tries can list words in order)
• Incremental search matters (keystroke-by-keystroke filtering)

Real applications don't perform single operations—they batch them. Let's analyze aggregate complexity.

Building a Trie from n Strings

If we insert n strings with lengths L₁, L₂, ..., Lₙ:

Total time: O(L₁ + L₂ + ... + Lₙ) = O(L), where L is the total length of all strings.

If average length is L̄ = L/n:

Total time: O(n × L̄) = O(nL̄)

Example:

• 1 million words, average length 8 characters
• Total: O(1,000,000 × 8) = O(8,000,000) character operations
• On modern hardware: milliseconds

Querying a Trie k Times

For k queries with lengths m₁, m₂, ..., mₖ:

Total time: O(m₁ + m₂ + ... + mₖ)

If query length is bounded by some constant M:

Total time: O(k × M) = O(k)

Key insight: Query time doesn't grow with trie size. A trie with 1 million words and a trie with 1 billion words answer queries in the same time.

The O(m) time guarantee comes with space considerations. Let's analyze the tradeoffs.

Array-Based Tries: Trading Space for Speed

Time: Absolute O(1) child lookup (single array access)

Space per node: O(Σ) where Σ is alphabet size

• 26 lowercase letters: 26 pointers = 208 bytes (64-bit)
• Full ASCII: 128 pointers = 1024 bytes
• Unicode: impractical

Total space: O(N × Σ) where N is total number of nodes

When to use: Small, fixed alphabet; speed-critical applications

Hash Map-Based Tries: Trading Speed for Space

Time: O(1) average, but with hashing overhead

• Hash computation for each character
• Potential hash collisions (rare but possible)

Space per node: O(actual children)

• Empty node: ~40-50 bytes (empty Map overhead)
• Node with k children: ~40 + (k × 16) bytes (entries)

Total space: O(N + edges) ≈ O(total characters)

When to use: Large or variable alphabets; memory-constrained applications

Compressed Tries (Radix Trees): Optimizing Space Further

Standard tries can waste space on single-child chains:

a → p → p → l → e  (5 nodes for "apple" with no branching)

Radix trees compress these chains:

"apple" (1 node with edge label "apple")

Trade-off:

• Space: Significantly reduced for sparse tries
• Time: Still O(m), but with larger characters per comparison
• Complexity: Implementation is more complex

We'll explore compressed tries in the advanced module.