Re: ArrayList BinarySearch vs Contains

Tech Tip: Click here to run a free scan for Windows Errors and optimize PC performance

Dave Sexton wrote:
Hi Bill,

It seems you are suggesting that the scale of the data can affect whether a
required sorting operation will actually reduce the overall performance of an
algorithm so that it becomes worse than a linear search. Can this be true
even when the data is sorted as it's being entered into the structure?


Yep, that's basically what he's saying. A good example of this is the
HybridDictionary. The HybridDictionary starts out as a ListDictionary
and then converts to a Hashtable when the number of items is large
enough. This works well despite the fact that the ListDictionary uses
a O(n) implementation as opposed to the Hashtable's O(1)
implementation. It would seem, based on the Big-Oh notation anyway,
that a Hashtable would always be faster, but what Big-Oh doesn't reveal
is the constant time factor which is significant in the case of a
Hashtable. Typically, a ListDictionary will outperform a Hashtable if
the number of items is less than 10.

.