sicp-ex-2.64


<< 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) = 2T(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).

atomik

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 roughly 2^n number 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?


anonymous

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


thanhnguyen2187

I found it easier explaining the whole process as steps:

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

jirf

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



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