1. Answer each short question (give precise value and the formula used) (20 points)

a) Given the 1000 data in the reverse sorted order (largest to smallest) and if you are using Insertion Sort, what will be the runtime.

b) What are the two steps of any recursive algorithm?

c) Given a set of 1000 sorted data. If you use Binary Search Tree algorithm to search for any key, what will be the runtime?

d) Given the tree as below: What will be the post order tree traversal sequence for the above tree?

e) Draw a Binary search tree using the following keys (no need to show the intermediate steps) 45, 100, 70, 15, 35, 29