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

This topic is 4484 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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 on other sites
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 on other sites
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 on other sites
Quote:
 Original post by red-dragonXFlarelocke--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 on other sites
Quote:
Original post by Flarelocke
Quote:
 Original post by red-dragonXFlarelocke--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 on other sites
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.

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 15
• 13
• 9
• 12
• 10
• ### Forum Statistics

• Total Topics
631442
• Total Posts
3000091
×