Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!sdd.hp.com!hplabs!hpcc05!hpwrce!kingsley
From: kingsley@hpwrce.HP.COM (Kingsley Morse)
Newsgroups: comp.theory
Subject: Re: C code for splay trees
Message-ID: <7360003@hpwrce.HP.COM>
Date: 28 Sep 90 14:20:09 GMT
References: <1990Sep26.223953.33593@eagle.wesleyan.edu>
Organization: Ye Olde Salt Mines
Lines: 19

Does anyone know how much cpu is needed to build a splay tree, and how much
cpu is needed to search a splay tree? For example, assume the splay tree 
has P patterns (or "records"), each pattern has D dimensions (or "keys"), 
and each record belongs to one of C classes (or "bins). Then the computational 
complexity of building a tree MAY be something like:

      cpu(build) = (PlnP)*(x**C)*D

and the computational complexity of searching a tree MIGHT be 

     cpu(search) = (lnP)*(x**C)

I've used "x" to denote a data dependent constant. 

If you're interested in this line of thought, you may want to participate in
the "Classification Clearinghouse" posting in sci.math.stat. 


                                                    Kingsley