Well, I know I cannot calculate exact time statistics, but I cen get information about the aproximate behavior - like the algorithm is Theta(n), Theta(n*log(n)), etc. It's quite sufficient, I think. According to your example - I don' know what you want to show, both algorithms are linear in time consumption: [reductions] length length2 l(10) 91 28 l(100) 721 73 l(1000) 7021 523 l(5000) 35021 2523 For length we get: 7*n+21 For length2 we get: 1/2*n+23 Thus, for both length and length' we get: Theta(n) And in my first e-mail, I wrote I knew it's not exact. But, if I expect behavior like Theta(n^2) and I can't fit it then I'm asking why - now I know answer even for that question (in my case) - I can provide only too small input to test (otherwise out of memory) and thus the curve is not "curve-enough" and is much closer to line. But new settings for hugs compilation should allowed much higher memory usage and I should get to more usable numbers. :-) Dusan Bulat Ziganshin wrote:
Hello Dusan,
Monday, August 29, 2005, 9:55:56 AM, you wrote:
Nevertheless, for the other algorithm the expected time complexity ( quite well known in general :-) ) and measured values do no fit together.
number of reductions is not exact time statistics. try the following alternative length definition ;)
length2 (_:_:_:_:_:_:_:_:_:_:xs) = (length2 xs)+10 length2 (_:xs) = (length2 xs)+1 length2 _ = 0
and compare number of reductions for:
length [1..5000] length2 [1..5000]
-- Dusan Kolar tel: +420 54 114 1238 UIFS FIT VUT Brno fax: +420 54 114 1270 Bozetechova 2 e-mail: kolar@fit.vutbr.cz Brno 612 66 Czech Republic --