Sign in to follow this  
red-dragonX

scheme procs and their 'big O' (time and space)

Recommended Posts

red-dragonX    122
I'm very horrible at determining time and space of procedures. Is time the one where it deals with deferred operations? and space, how much memory? I know there is linear O(n), exponential O(2 ^ n), log, and O(1). I'm not exactly sure how you go about computing the space and time (in class it makes sense, but I"ll be damned if I can figure out alone at home). Another question I have is about the words 'tail recursive' and 'iterative process'. What does tail recursive actually mean? (Is it when a proc is written without deferred operation?) TIA. --------------------------------------------------- Yeah, loads of questions. Now, here's the next set: ;For each proc below determine big O. Assume append and reverse are ;both iterative processes. ;Which are tail recursive? ;Which of these will be faster? ;Amplify takes a factor and a list of numbers. It returns a new list ;of the numbers multiplied by factor.
(define amplify-R
  (lambda (n alist)

    (define amplify-iter-R
      (lambda (n elts new)
        (cond ((null? elts) new)
              (else (amplify-iter-R n (cdr elts) (cons (* n (car elts)) new))))))

    (reverse (amplify-iter-R n alist ()))))


(define amplify-iter-A
  (lambda (n elts new)
    (cond ((null? elts) new)
          (else (amplify-iter-A n (cdr elts) (append new (list (* n (car elts)))))))))


(define amplify-iter-R
  (lambda (n elts new)
    (cond ((null? elts) (reverse new))
	  (else (amplify-iter-R n (cdr elts) (cons (* n (car elts)) new))))))
[Edited by - red-dragonX on March 16, 2006 9:11:36 AM]

Share this post


Link to post
Share on other sites
Flarelocke    410
In general recursive functions, you need a stack to hold the past arguments. In tail recursive functions, by the time you recurse, you're done using all of the past arguments, so you can get rid of them and hence, you don't need a stack. This makes tail-recursive functions equivalent to an iterative loop.

To calculate the time complexity of a function, you add up all the times you do an operation. For a loop, the body of which is executed once for each iteration of the loop, this becomes multiplication of the complexity of the body times the number of iterations. For function calls, the time complexity is the complexity of the called function.

Space complexity is similar, but a bit more complicated.

I think by iterative process, they mean that it's linear in the length of its argument.

Share this post


Link to post
Share on other sites
red-dragonX    122
Flarelocke--the explanation is nice, but I'm kinda stuck at the moment.

Can anyone answer the bottom half after "-----" part? For anyone who does give me the big O, can you give me the reasoning behind what your answer is? I'd REALLY appreciate it.

Share this post


Link to post
Share on other sites
Flarelocke    410
Quote:
Original post by red-dragonX
Flarelocke--the explanation is nice, but I'm kinda stuck at the moment.

Can anyone answer the bottom half after "-----" part? For anyone who does give me the big O, can you give me the reasoning behind what your answer is? I'd REALLY appreciate it.


Would you mind reposting with source or code tags please? Without them, the code looks like it's all flat, which makes scheme especially difficult to read.

Share this post


Link to post
Share on other sites
red-dragonX    122
Quote:
Original post by Flarelocke
Quote:
Original post by red-dragonX
Flarelocke--the explanation is nice, but I'm kinda stuck at the moment.

Can anyone answer the bottom half after "-----" part? For anyone who does give me the big O, can you give me the reasoning behind what your answer is? I'd REALLY appreciate it.


Would you mind reposting with source or code tags please? Without them, the code looks like it's all flat, which makes scheme especially difficult to read.


done (code tags..)

Share this post


Link to post
Share on other sites
Flarelocke    410
Quote:
Original post by red-dragonX
;For each proc below determine big O. Assume append and reverse are
;both iterative processes.

;Which are tail recursive?

;Which of these will be faster?

;Amplify takes a factor and a list of numbers. It returns a new list
;of the numbers multiplied by factor.


(define amplify-R
(lambda (n alist)

(define amplify-iter-R
(lambda (n elts new)
(cond ((null? elts) new)
(else (amplify-iter-R n (cdr elts) (cons (* n (car elts)) new))))))

(reverse (amplify-iter-R n alist ()))))


Let the time taken by amplify-iter-R be represented as TiR,n, where n is the length of elts Then:

TiR,n = TiR,n-1 + Tcdr + Tcar + T* + Tcons

We don't really care all that much about how long cdr, cons, *, and car take as long as they don't depend on the length of our list, so we can just represent any or all of them as O(1). The sum of two big-O expressions is the max of the two, so O(1) + O(1) = O(1). Our formula then becomes:

TiR,n = TiR,n-1 + O(1)

Since this formula will end up adding these constants n times (or more generally, O(n) times), the expression will be O(n). Making it more rigorous would require me to break out the definition of big-O. You just need to know that these sorts of expressions become products (i.e. O(n*1)).

The outer function can be expressed like this:
TR,n = TiR,n + Treverse

Assuming reverse is a linear time algorithm:
TR,n = O(n) + O(n) = O(n)

Space complexity is done similarly, but you have to figure out when a value is no longer needed because if a variable is no longer needed, it can be garbage collected, which means the space complexity of an enclosing algorithm is not a straightforward sum of the functions it calls.

Tail recursion means that the values that used to be the formal parameters can be thrown away as new values are copied into their place. This gives a constant space complexity for a function, even while the time complexity is linear or higher.

AFAICT all your recursive functions are tail recursive. A handy rule-of-thumb is that if the result of the outer function is exactly the result of the inner function (i.e. no computations after the inner function is done), the function is tail-recursive.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this