MOO-cows Mailing List Archive

[Subject Prev][Subject Next][Thread Prev][Thread Next][Subject Index][Thread Index]

re:hash & balanced trees

On Mon, 30 Jun 1997, Amy Bruckman wrote:

> Subject : Re: my kingdom for a hash table! 
> ----- Message Text -----
> ..., something about operations increasing exponentialy, ...
The computational complexity of most algorithms over particular data 
structures is provable.  The computational complexity for searching a 
linear list for a specified string is on the order of the number of 
elements in the list and is often denoted O(n).  If the list is kept in
a sorted fashion, algorithms can achieve greater efficency than O(n/2).
Of course, there is a greater cost of adding an element to a sorted list
than to an unordered list.  This tradeoff, between computation required to
create and maintain a data structure and the complexity of searching for
an element, is a primary issue when considering alternative structures.

Balanced binary trees are O(log(n)) on searches, and algortithms such as AVL
trees have acceptable insertion and deletion measures.  Besides, there is c
source code available.


Follow-Ups: References:
Home | Subject Index | Thread Index