CMSC 341
Fall 2001 -- Project 4

These questions relate to the data your program reported.  If you failed to
get a working program, use the data in sample output (Mr. Frey's p4output
file) to answer these questions.

1. (10 points)  Explain how the observed BST data supports 
(or fails to support) the theoretical asymptotic running time for the 
insert and find operations. Be sure your analysis includes but is not limited
to a discussion of the theoretical asymptotic performance and to the answers 
these questions
       A. What significance is the value C / M * lgN ?
       B. What did you expect to see for C / M * lgN?
       C. How does the value of C / M * lgN support or fail to support
the theoretical performance?

2. (10 points)  Explain how the observed Splay Tree data supports 
(or fails to support) the theoretical asymptotic running time for the 
insert and find operations. Be sure your analysis includes but is not limited 
to a discussion of the theoretical asymptotic performance and to the answers 
these questions
       A. What significance is the value C / M * lgN ?
       B. What did you expect to see for C / M * lgN?
       C. How does the value of C / M * lgN support or fail to support
the theoretical performance?