title: Tree-recursive / time complexity Scheme assignment
body: <p>If you could help me with ANY part of this question, I would appreciate it. Thanks.</p>
  
  <pre><code>2^0 = 1
  2^N = 2^(N-1) + 2^(N-1)
  </code></pre>
  
  <ol>
  <li><p>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.</p></li>
  <li><p>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.</p></li>
  <li><p>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.</p></li>
  <li><p>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.</p></li>
  </ol>
  
  <p>Here's the template:</p>
  
  <pre><code>;; to-the-power-of: integer integer -&gt; integer
  ;; This function raises m to the power of n, returning the result.
  ;; m must be &gt; 0 and n &gt;= 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
  </code></pre>
  
  <p>We'll add one more restriction: you can't use the * operator; you can only use the following recursive function to do multiplications:</p>
  
  <pre><code>;;; multiply: integer integer -&gt; integer
  ;; This function multiplies two non-negative integers, returning the result.
  ;; Its time complexity is O(a).
  (define (multiply a b)
    ...) 
  </code></pre>
  
  <p>Write the function, and describe what its time complexity is and why.</p>