[Haskell-cafe] Re: appending an element to a list

[Martin Geisler]

Tillmann Rendel <rendel at daimi.au.dk> writes:

Hi! (Cool, another guy from DAIMI on haskell-cafe!)

> Another (n - 1) reduction steps for the second ++ to go away.
>
>         last ("o" ++ "l")
> A)  ~>  last ('o' : "" ++ "l"))
> L)  ~>  last ("" ++ "l")
> A)  ~>  last ("l")
> L)  ~>  'l'
>
> And the third and fourth ++ go away with (n - 2) and (n - 3) reduction
> steps. Counting together, we had to use
>
>   n + (n - 1) + (n - 2) + ... = n!
>
> reduction steps to get rid of the n calls to ++, which lies in O(n^2).
> Thats what we expected of course, since we know that each of the ++
> would need O(n) steps.

I really liked the excellent and very clear analysis! But the last
formula should be:

   n + (n - 1) + (n - 2) + ... = n * (n+1) / 2

which is still of order n^2.

-- 
Martin Geisler

VIFF (Virtual Ideal Functionality Framework) brings easy and efficient
SMPC (Secure Multi-Party Computation) to Python. See: http://viff.dk/.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 188 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20080530/9be87f4f/attachment.bin