Time & Space Complexity in Tries
Time Complexity
- Insert:
O(n)where n: no. of character in words. - Search:
O(n)where: n = no. of character in words. - Prefix:
O(P)where: p = no. of words in prefix.
Space Complexity
O(total character)
speed >>> space
In a Trie data structure, the space complexity is relatively high, but this trade-off is acceptable because it provides much faster search performance.
When to use Trie Data Structure?
- Prefix Search: All words that starts with ‘any letter’.
- Auto Complete
- Dictionary-based problems
- Word Suggestions
- Spell Checking
Whe NOT to use Trie Data Structure?
- Exact Search
- Memory Constraints
- Dataset is small
In such cases, a HashMap is a better approach.
