SICP 2.64 order of growth of recursive procedure

Question

I am self-studyinig SICP and having a hard time finding order of growth of recursive functions.

The following procedure list->tree converts an ordered list to a balanced search tree:

(define (list->tree elements) 
  (car (partial-tree elements (length elements)))) 

(define (partial-tree elts n) 
  (if (= n 0) 
      (cons '() elts) 
      (let ((left-size (quotient (- n 1) 2))) 
        (let ((left-result (partial-tree elts left-size))) 
          (let ((left-tree (car left-result)) 
                (non-left-elts (cdr left-result)) 
                (right-size (- n (+ left-size 1)))) 
            (let ((this-entry (car non-left-elts)) 
                  (right-result (partial-tree (cdr non-left-elts) 
                                              right-size))) 
              (let ((right-tree (car right-result)) 
                    (remaining-elts (cdr right-result))) 
                (cons (make-tree this-entry left-tree right-tree) 
                      remaining-elts))))))))

I have been looking at the solution online, and the following website I believe offers the best solution but I have trouble making sense of it:

jots-jottings.blogspot.com/2011/12/sicp-exercise-264-constructing-balanced.html

My understanding is that the procedure 'partial-tree' repeatedly calls three argument each time it is called - 'this-entry', 'left-tree', and 'right-tree' respectively. (and 'remaining-elts' only when it is necessary - either in very first 'partial-tree' call or whenever 'non-left-elts' is called)

this-entry calls : car, cdr, and cdr(left-result)
left-entry calls : car, cdr, and itself with its length halved each step
right-entry calls: car, itself with cdr(cdr(left-result)) as argument and length halved

'left-entry' would have base 2 log(n) steps, and all three argument calls 'left-entry' separately. so it would have Ternary-tree-like structure and the total number of steps I thought would be similar to 3^log(n). but the solution says it only uses each index 1..n only once. But doesn't 'this-entry' for example reduce same index at every node separate to 'right-entry'?

I am confused.. Further, in part (a) the solution website states:

"in the non-terminating case partial-tree first calculates the number of elements that should go into the left sub-tree of a balanced binary tree of size n, then invokes partial-tree with the elements and that value which both produces such a sub-tree and the list of elements not in that sub-tree. It then takes the head of the unused elements as the value for the current node"

I believe the procedure does this-entry before left-tree. Why am I wrong?

This is my very first book on CS and I have yet to come across Master Theorem. It is mentioned in some solutions but hopefully I should be able to do the question without using it.

Thank you for reading and I look forward to your kind reply,

Chris

Will Ness Will Ness · Accepted Answer · 2014-12-04T13:42:53

You need to understand how let forms work. In

          (let ((left-tree (car left-result)) 
                (non-left-elts (cdr left-result))

left-tree does not "call" anything. It is created as a new lexical variable, and assigned the value of (car left-result). The parentheses around it are just for grouping together the elements describing one variable introduced by a let form: the variable's name and its value:

          (let (  (   left-tree      (car left-result)  ) 
          ;;      ^^                                   ^^
                  (   non-left-elts  (cdr left-result)  )
          ;;      ^^                                   ^^

Here's how to understand how the recursive procedure works: don't.

Just don't try to understand how it works; instead analyze what it does, assuming that it does (for the smaller cases) what it's supposed to do.

Here, (partial-tree elts n) receives two arguments: the list of elements (to be put into tree, presumably) and the list's length. It returns

            (cons (make-tree this-entry left-tree right-tree) 
                  remaining-elts)

a cons pair of a tree - the result of conversion, and the remaining elements, which are supposed to be none left, in the topmost call, if the length argument was correct.

Now that we know what it's supposed to do, we look inside it. And indeed assuming the above what it does makes total sense: halve the number of elements, process the list, get the tree and the remaining list back (non-empty now), and then process what's left.

The this-entry is not a tree - it is an element that is housed in a tree's node:

            (let ((this-entry (car non-left-elts))

Setting

                  (right-size (- n (+ left-size 1))

means that n == right-size + 1 + left-size. That's 1 element that goes into the node itself, the this-entry element.

And since each element goes directly into its node, once, the total running time of this algorithm is linear in the number of elements in the input list, with logarithmic stack space use.

SICP 2.64 order of growth of recursive procedure

1 Answers