title: What is the Best/Worst/Average Case Big-O Runtime of a Trie Data Structure?
body: <p>What is the best/worst/average case complexity (in Big-O notation) of a trie data structure for insertion and search?</p>
  
  <p>I think it is <code>O(K)</code> for all cases, where <code>K</code> is the length of an arbitrary string which is being inserted or searched.  Will someone confirm this?</p>