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

# re:hash & balanced trees

- Date: Mon, 30 Jun 1997 23:28:59 -0400 (EDT)
- From:
- Content-Type: TEXT/PLAIN; charset=US-ASCII
- In-Reply-To: <9707010118.AA01082@kilpikonna.media.mit.edu>

    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.

    more,
    l8r,
    v

Follow-Ups:

- re:hash & balanced trees

- From: Richard Godard <janus@cam.org>

- re:hash & balanced trees

- From: Michael Brundage <brundage@piaf.ipac.caltech.edu>

References:

- Re: my kingdom for a hash table!

- From: Amy Bruckman <asb@media.mit.edu>

- Prev by Subject: Re: Hacking the parser
- Next by Subject: re:hash & balanced trees
- Prev by thread: Re: my kingdom for a hash table!
- Next by thread: re:hash & balanced trees
- Index(es):
  - Subject
  - Thread

Home | Subject Index | Thread Index