On Sep 17, 2014, at 2:04 AM, mukesh tiwari wrote: > Dear Racket Users, > I am learning racket and I found little bit misleading statement on guide > [1]. It says that "Both the my-length and my-map functions run in O(n) time > for a list of length n.". Technically this statement is correct but when I > read below > > "For a list with n elements, evaluation will stack up n (+ 1 ...) additions, > and then finally add them up when the list is exhausted. > > You can avoid piling up additions by adding along the way. To accumulate a > length this way, we need a function that takes both a list and the length of > the list seen so far; the code below uses a local function iter that > accumulates the length in an argument len". > > so just curious, shouldn't it be "Both the my-length and my-map functions run > in O(n) space for a list of length n." ? >
That's correct for straightforward versions of these functions. -- Matthias
____________________ Racket Users list: http://lists.racket-lang.org/users
