Binary Search Tree Project

1. Estimate the asymptotic running time of searching in a skewed BST and a balanced BST. Justify your conjecture explaining which operations of the BinarySearchTree class (attached) you would use, and explain how do you obtain the overall running time from the running times of those operations. You can use asymptotic notation (big-O).

2. Write a program to do the following. Input an integer x. (Should work with big numbers.) Create a completely-skewed BST S containing 1,2,...,x. Create a BST R containing x integers without repetitions gen- erated at random. (To minimize the risk of repetitions, you can multiply the value returned by random() by a big number.) Given that the numbers are generated uniformly at random, the tree will likely be balanced. Measure the time to search in S for a number that is not in the tree. Measure the time to search in R for a new random number. Display the time taken for each search.

Fill in a chart like in the photo attached with the times in nanoseconds measured. You may need to adjust the values of n according to your plat- form. That is, if your program takes too long to complete, or if you run out of memory, etc., reduce the range of n as needed. Your chart must have enough cells lled to be able to answer the following question.

3. How the results obtained compare with your conjecture? If the results dier from your conjecture, investigate the reason by looking carefully at the code of the BinarySearchTree class, and explain what happened.

Fill in a chart like the following with the times in nanoseco sured. You may need to adjust the values of n according to form. That is, if your program takes too long to complete, o out of memory, etc., reduce the range of n as needed have enough cells filled to be able to answer the following qu . Your n= 10 | n = 10 n 100 | n = 10 | Skewed BST Balanced BST Fill in a chart like the following with the times in nanoseco sured. You may need to adjust the values of n according to form. That is, if your program takes too long to complete, o out of memory, etc., reduce the range of n as needed have enough cells filled to be able to answer the following qu . Your n= 10 | n = 10 n 100 | n = 10 | Skewed BST Balanced BST