<< 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).

<< 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?