Here is an exercise from SICP (Structure and Interpretation of Computer Programs):
Exercise 2.63: Each of the following two procedures converts a binary tree to a list.
(define (tree->list-1 tree) (if (null? tree) '() (append (tree->list-1 (left-branch tree)) (cons (entry tree) (tree->list-1 (right-branch tree)))))) (define (tree->list-2 tree) (define (copy-to-list tree result-list) (if (null? tree) result-list (copy-to-list (left-branch tree) (cons (entry tree) (copy-to-list (right-branch tree) result-list))))) (copy-to-list tree '()))... 2. Do the two procedures have the same order of growth in the number of steps required to convert a balanced tree with n elements to a list? If not, which one grows more slowly?
Looking at both procedures and without doing any computations for the order of growth, all elementary operations of tree->list-2 are constant, while one of the operation in tree->list-1, append, is not. So it is very clear that tree->list-2 grows more slowly than tree->list-1.
Now, although the exercise did not specifically asks us to do so, I would like to find the order of growth in the number of steps of tree->list-1. The following is my attempt.
The append procedure is:
(define (append list1 list2)
(if (null? list1)
list2
(cons (car list1)
(append (cdr list1)
list2))))
From the definition, the order of growth in the number of steps grows as theta(l1) where l1 is the number of elements in the first list. If two lists has the same length, then the order of growth grows as theta(n/2) where n is the sum of the number of elements of both lists. Based on these, I try to calculate the order of growth of tree->list-1 like this:
Suppose append takes constant time (just for initial), then we will find that the order of growth of tree->list-1 grows as theta(n). Since append is the only procedure that is not constant, I believe I can safely ignore other elementary operations. With the real running time of append, I got the following observations.
Note: The trees in my observations are balanced. So I experimented with the running times by doubling the number of nodes (or incrementing the height of the tree).
0 nodes - constant
1 node - constant
3 nodes - 1 recursive call to append
7 nodes - 5 recursive calls to append (first 2 are from subtrees (above), 3 are from the left branch)
15 nodes - 17 recursive calls to append (10 are from subtrees (above), 7 are from the left branch)
31 nodes - 49 recursive calls to append (34 are from subtrees (above), 17 are from the left branch)
63 nodes - 129 recursive calls to append (98 are from subtrees (above), 31 are from the left branch)
...
n nodes - 2t+(n/2) where t is the number of steps of the subtrees and n is the number of nodes in the tree
My additional observations are: In a completely unbalanced binary tree: If all nodes are in the right branch, the number of steps grows as theta(n). If all nodes are in the left branch, the number of steps grows as something like (1+2+3+4+...+n-1) probably like n(n-1)/2 (I found this formula somewhere). Based on my data, the number of steps in a balanced binary tree grows somewhere in between.
Now, the sequence of number of steps as the number of nodes doubles is: (1, 5, 17, 49, 129). And they grow as (4, 12, 32, 80).
It seems that we get the number of steps of a balanced binary tree with n elements by: 2t+(n/2) where t is the number of steps of two subtrees and n is the number of nodes.
Now for the life of me, I cannot find the classification this order of growth belongs to (E.G. linear, logarithmic, quadratic, exponential) though I have confirmed that this order of growth grows faster than linear and grows slower than quadratic.
Is my data correct? Have I found the order of growth of tree->list-1 as n increases even though I cannot classify it?
(append '() (cons entry ...)). Any reasonable implementation of append will efficiently return the right argument. The interesting case is then the balanced one in between. - Kazreduce. - Kaz