Homework #9    COSC 311		
Distributed 4/9/2013    Due: 4/16/2013



To search a self-balancing binary search tree, requires O(log n). (log is base 2)

To search a B tree order 54, requires O(log n) (log is base 54)


Suppose the time for retrieval of a single node is 100 ns. 

1. How many data items (n) must be in the tree before you notice a difference 
in retrieval time of approximate 5 minutes?

2. For n the value you determined in the first question, how many nodes
are in each tree (the BST and the B tree)? -- Assume the trees are append only
(no deletions)

3. For n the number of data items you determined in (1), what percentage of
the total space required for each tree is used to maintain the data structure
(i.e., not used for actual data). Assume the following:
pointer:  6 bytes
data record: 122 bytes



N.B. This problem does NOT assume efficient use of sector space on secondary
storage.