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

> >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