North American Network Operators Group
Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical

RE: register.com down sev0?

  • From: Tony Li
  • Date: Fri Oct 27 19:31:35 2006 
 

> Nah. You assume branching factor of 2 (and not radix tree but 
> rather a 
> form of binary tree, i.e. AVL, r/b or Patricia - they have that 
> O(log2(num_entries)) behaviour, while radix trees are traversed in 
> O(key_length/branching_factor)).


I assumed a binary radix trie (not tree) because that's the normal
cannonical version used by computer science students.  Yes, as you
outlined, there are many games you can play, if you're willing to make
space/time tradeoffs.

Regardless of the details, the point remains: if your data structures
are largely constant, then you are more efficient searching a small data
set vs. searching a large one.

Tony