Upper bound for number of nodes in a trie?

Revision en1, by sayeef006, 2021-12-03 21:08:04

Can we estimate the upper bound of number of nodes of a trie? I'm using the array based implementation of trie, so i have to declare an array with the highest number of nodes, i know when inserting 32bit numbers the node count cant be greater than (N*32), but the actual upper bound should be way less right? Because for each node there are only two options for the next node? Am I right on this and if i am, can we estimate that value?

Tags trie

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English sayeef006 2021-12-03 21:08:04 483 Initial revision (published)