I'm interested in knowing the runtime complexity of the DataTable.Find
method in 2.0 when attempting to find a row by the primary key. The
MSDN documentation is vague...probably intentionally. I used .NET
Reflector to examine the DataTable and what I found is that the
primary key index is implemented with a red black tree. That leads to
be believe that the operation is O(log n) unless something else was
going on that I missed. I'm a little disappointed that a O(1)
algorithm isn't used, but I can understand the reasoning behind the
BST since it keeps the index in a sorted order. Can anyone else
confirm?

On Jul 11, 9:55 am, Brian Gideon <briangid...@yahoo.com> wrote:
> I'm interested in knowing the runtime complexity of the DataTable.Find
> method in 2.0 when attempting to find a row by the primary key. The
> MSDN documentation is vague...probably intentionally. I used .NET
> Reflector to examine the DataTable and what I found is that the
> primary key index is implemented with a red black tree. That leads to
> be believe that the operation is O(log n) unless something else was
> going on that I missed. I'm a little disappointed that a O(1)
> algorithm isn't used, but I can understand the reasoning behind the
> BST since it keeps the index in a sorted order. Can anyone else
> confirm?

As a follow up I presume calling
DataTable.DefaultView.ApplyDefaultSort = true is O(1) since the
primary key is already sorted?