Question 1 Lower bounds. Part A Given is a sorted list of ten integers, and two additional integers x and y. All integers are different. Create a sorted list of twelve elements. Part B Given are sorted lists of twenty and seven integers respectively.
All integers are different.
Create a sorted list of 27 elements. Think about this more generally. Let A be a sorted list of n elements, let B be a sorted list of m elements, and let C be an unsorted list of k elements. Question 2 Recurrences, trees. Solution Let h be the height of the tree.