<< Previous exercise (2.63) | Index | Next exercise (2.65) >>

**a.** PARTIAL-TREE splits the list ELTS into three parts: the median item THIS-ENTRY, the list of items less than the median, and the list of items greater than the median. It creates a binary tree whose root node is THIS-ENTRY, whose left subtree is the PARTIAL-TREE of the smaller elements, and whose right subtree is the PARTIAL-TREE of the larger elements.

5 / \ 1 9 \ / \ 3 7 11

**b.** At each step, PARTIAL-TREE splits a list of length *n* into two lists of approximate length *n* ÷ 2. The work done to split the list is (QUOTIENT (- N 1) 2) and (- N (+ LEFT-SIZE 1)), both of which take constant time. The work to combine the results is (MAKE-TREE THIS-ENTRY LEFT-TREE RIGHT-TREE), and is also constant. Therefore, the time to make the partial tree of a list of *n* elements is:

*T*(*n*) = 2*T*(*n* ÷ 2) + Θ(1)

By the Master Theorem, we have *a* = 2, *b* = 2, and *f*(*n*) = Θ(1). Therefore, *T*(*n*) = Θ(*n*).

The time taken by LIST->TREE for a list of length *n* will be the time taken by PARTIAL-TREE plus the time taken by LENGTH for that list. Both procedures have order of growth Θ(*n*), so the order of growth of LIST->TREE is Θ(*n*).

To atomik. It is certain that the procedure `parital-tree` is called O(2^**d**) times with respect to the **depth d** of the calling tree. However, in terms of the **the size of the input n**, the calling tree looks like:

n / \ n/2 n/2 / \ / \ n/4 n/4 n/4 n/4 ... ... ...

There are O(2n-1) nodes, and the cost is O(1) at each node. Therefore, the total cost is Θ(n).

I found it easier explaining the whole process as steps:

- Split the elements into left half, middle element, and right half
- Build the left tree with the left half
- Build the right tree with the right half
- Return a built tree with the middle element, the left tree, and the right tree

Here is a result table for easier referencing (please copy the text to a wider screen, or to a Markdown previewer):

| n | elts | left-size | left-result | left-tree | right-size | right-result | right-tree | non-left-elts | | - | ---- | --------- | ----------- | --------- | ---------- | ------------ | ---------- | ------------- | | 1 | (3 5 7 9 11) | 0 | (() 3 5 7 9 11) | () | 0 | (() 5 7 9 11) | () | (3 5 7 9 11) | | 2 | (1 3 5 7 9 11) | 0 | (() 1 3 5 7 9 11) | () | 1 | ((3 () ()) 5 7 9 11) | (3 () ()) | (1 3 5 7 9 11) | | 1 | (7 9 11) | 0 | (() 7 9 11) | () | 0 | (() 9 11) | () | (7 9 11) | | 1 | (11) | 0 | (() 11) | () | 0 | (()) | () | (11) | | 3 | (7 9 11) | 1 | ((7 () ()) 9 11) | (7 () ()) | 1 | ((11 () ())) | (11 () ()) | (9 11) | | 6 | (1 3 5 7 9 11) | 2 | ((1 () (3 () ())) 5 7 9 11) | (1 () (3 () ())) | 3 | ((9 (7 () ()) (11 () ()))) | (9 (7 () ()) (11 () ())) | (5 7 9 11) |

*a.*

The *partial-tree* function relies on the ease of calculating the trivial case of a tree containing zero elements, and the ability to calculate the size of left/right sub-trees with mere arithmetic. The function recurses first down the left sub-trees by (partial-tree ents left-size). When n=1, left/right-size=0 so left/right-result= ('() . ents), this-entry=(car ents), remaining-ents=(cdr ents). All are correct. This correct left-result means the calling function receives the correct left-tree, remaining-ents, and can correctly calculate right tree with (partial-tree remaining-ents right-size). As with the next calling function, ad infinitum.

5 1 9 nil 3 7 11 nil nil nil nil nil nil

*b.*

I believe that *partial-tree* is O(n) but math is not my strong suite and I found this quite tricky

Assuming that elts is at least n-elements long the number of steps to calculate the result of any call to *partial-tree* is dependent on n.

For any n > 0 calculating *(partial-tree elts n)* requires calculating

(partial-tree elts (quotient (- n 1) 2) (partial-tree (cd..dr elts) (- n (+ left-size 1)))

The new n parameters are ~n/2.

Here is a tree showing the structure of the recursive calls.

1.n=x 1.n=~(x/2) 2.n2=~(x/2) 1.n=~(x/4) 2.n=~(x/4) 3.n=~(x/4) 4.n=~(x/4) dot dot dot 1.n=1 2.n=1 dot dot dot 2^(log2(n)).n=1 1.n=0 2.n=0 dot dot dot 2^(log2(n)+1).n=0

The height of this pyramid is ~log2(n)+1 because n (basically) halves 2 twice at each stage until it hits n=1, then it becomes 0 twice. To calculate the total number of calls to *partial-tree* we notice we are adding the widths of the ~log2(n)+1 levels of the pyramid.

This boils down to (sum from=0 to=~log2(n)+1 k=2^x). If I remember correctly the answer to that summation of 2^x from 0 to x is 2^(x+1) - 1. Therefore the number of steps is

- O(~2^(log2(n)+2)-1) ->
- O(~2^(log2(n))*(2^2)) ->
- O(~n*4) ->
- O(n)

I think the discussion above on part a) is lacking. I, for one, was very skeptical of the correctness of this algorithm till I did some tests on paper and then and framed it in precise english:

'(partial-tree elems n)' -> "To create a binary tree from 'n' elements of list 'elems'..."

- [base case] a binary tree on no elements (empty list or n=0) is nil
- split the list into
*[<left-half>, middle-element, <right-half>]* - [subproblem] create a binary tree for the left half, i.e. '(partial-tree left-half (length left-half))'
- [subproblem] create a binary tree for the right half, i.e. '(partial-tree right-half (length right-half))'
- return a new binary tree, rooted at 'middle-element', with the left tree at its left and its right tree at its right.

I was still skeptical at this point; "is that *it*, shouldn't there be more magic?!". The way to convince yourself that this works is to prove that it's true for n=1 through n=3, and then show that it generalizes from there (i.e., an inductive proof). It's pretty cool once you understand it.

<< Previous exercise (2.63) | Index | Next exercise (2.65) >>

I got a different answer by setting breakpoints in the drracket debugger and stepping through the program. The number of stack frames hovered around

log_2(n), and the `partial-tree` function was recursively called roughly2^nnumber of times. That lead me to believe that the orders of growth are:Space: O(log_2(n))Time: O(2^n)I realize my answer is very different from the one given above. Did I do something wrong?