Help with this tree-recursive / time complexity Scheme problem?

Question

If you could help me with ANY part of this question, I would appreciate it. Thanks.

2^0 = 1
2^N = 2^(N-1) + 2^(N-1)

1. Convert this definition into an exactly equivalent tree-recursive function called two-to-the-power-of. Describe its asymptotic time complexity and explain why it has this time complexity.

2. Now write a function called tttpo_rec which computes the exact same thing, but which uses a linear recursive process which has an O(n) time complexity and also uses O(n) space for its pending operations.

3. Now write a function called tttpo_iter which computes the exact same thing, but which uses a linear iterative process which has an O(n) time complexity and also uses constant space.

4. Now let's say you want to generalize one of the preceding definitions so that it will handle arbitrary integer powers, so that you can compute 2^N, 3^N etc. Write a function called to-the-power-of that takes two arguments and raises one to the power of the other.

Here's the template:

;; to-the-power-of: integer integer -> integer
;; This function raises m to the power of n, returning the result.
;; m must be > 0 and n >= 0.
(define (to-the-power-of m n)
  ...)

(check-expect (to-the-power-of 1 0) 1) ; base case
(check-expect (to-the-power-of 2 3) 8) ; recursive case
(check-expect (to-the-power-of 3 2) 9) ; recursive case

We'll add one more restriction: you can't use the * operator; you can only use the following recursive function to do multiplications:

;;; multiply: integer integer -> integer
;; This function multiplies two non-negative integers, returning the result.
;; Its time complexity is O(a).
(define (multiply a b)
  ...)

Write the function, and describe what its time complexity is and why.

Answer 1

I like your homework. I won't do it for you though.

And given how you "asked", I don't see possibilities to give you helpful hints without doing it.

What do you expect?

Answer 2

Hahahaha. I shouldn't do homework problems for people, but this is too fun. :-P

1. This is just the naive implementation. I can answer this without giving the rest of the questions away.

   (define (tttpo n)
     (if (zero? n) 1
                   (+ (tttpo (- n 1)) (tttpo (- n 1)))))
   

   Obviously this is a really stupid implementation, but you're asked to give its asymptotic complexity.

2. Think of how to avoid calling tttpo twice per iteration. Since you're asked to avoid using *, you may need to stash the result of tttpo.

3. Read up on tail recursion. To be specific, you need to know how to convert a general recursive algorithm to its equivalent iterative (or tail-recursive, since this is Scheme) version.

4. Obvious once you've written the code for 3. (Or else, show me your answer to 3 and I'll help you further.)

Good luck!

Answer 3

The first algorithm is O(2^n), and can be written as follows:

(define (2pow x)
  (if (= x 0) 1
      (+ (2pow (- x 1))
         (2pow (- x 1)))))

This can be rewritten in O(n) as follows:

(define (2pow x)
  (if (= x 0) 1
    (* 2 (2pow (- x 1)))))

Since Scheme uses tail call optimization, we can write this as a tail-recursive function that takes up constant stack:

(define (2pow x)
  (define (internal x accum)
    (if (= x 0) accum
        (internal (- x 1) (* accum 2))))
  (internal x 1))

Generalized:

(define (to-the-power-of a b)
  (define (internal x accum)
    (if (= x 0) accum
        (internal (- x 1) (* accum a))))
  (internal b 1))

edit: since I see you can't use *, you can just write your own integer multiplication:

(define (mult a b)
  (define (internal a accum)
    (if (= a 1) accum
        (internal (- a 1) (+ accum b))))
  (internal a b))

This is tail-recursive, so it runs in constant stack space. Just replace * with mult in any of the above algorithms.

I should also note that all these functions were written directly here into the editor without being tested. use at your own risk

Answer 4

@dave,

What did you do to solve this problem? Do you expect to get solution for your homework here? People don't mind to help if you're tried to solve this yourself but failed at some step. In current version this is not a real question, it's just an attempt to avoid doing your work.

IMO people should not encourage laziness and provide solution for homework. Doing real-world job, do you ask your colleagues to solve your task instead of doing it on your own?