Re: Re: HOWTO: convert flat list w/ level information

>From the data given the relationship is exponential not quadratic.



----- Original Message ----- 
From: "David Tolpin" <dvd@xxxxxxxxxxxxxx>
To: <xsl-list@xxxxxxxxxxxxxxxxxxxxxx>
Sent: Wednesday, December 03, 2003 10:48 AM
Subject: Re:  Re: HOWTO: convert flat list w/ level information to a
hierarchial one?u


> > >Look, the time is exponential.
> >
> > I'll believe that it's quadratic, but I think it's most unlikely to be
> > exponential.
> >
> > O(2^n) is not the same as O(n^2)!
> >
>
> If data is two times longer, the computation time is 4 times longer with
quadratic
> dependence, right? With the alogirthm that uses unlimited lookahead it is
> 100 ms for 100 nodes
> 1000 ms for 200 nodes
> according to Dimitre's data.
>
> My testing environment is 100 times slower.
>
> 10 s for 100 nodes
> 32 s for 150 nodes
> 120 s for 200 nodes
> 350 s for 250 nodes
> 920 s for 300 nodes
>
> Looks like exponential. Time grows 3 times with each additional 50 nodes.
> This is with SAXON 6.5.3, JDK 1.3.1/FreeBSD, Pentium II 700MHz. Deviations
> are due to garbage collection, I think.
>
> Although I was never formally taught the theory of algorithms, I will try
to provide
> a formal proof.
>
> David
>
>
>
>
>  XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
>


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list