14 Feb
2006
14 Feb
'06
9:42 p.m.
On Mon, Feb 13, 2006 at 08:21:04PM +0200, Härmel Nestra wrote:
Making experiments with the length varying leads to the suggestion that minimum [1 .. n] runs in quadratic time on n while minimum [n, n - 1 .. 1] runs in linear time.
OK, what's happening is that in Hugs, functions that return one of their arguments, like min x y = if x <= y then x else y return an indirection to the argument (to avoid copying it), so these examples traverse a chain of indirections that gets longer for each new min, hence the quadratic behaviour. This is now fixed in CVS (no need to create an indirection pointing at an indirection). Thanks for the analysis.