1. What would happen if you called "InsertItem"defined for a list that already contains two elements whose keys are "EQUAL" to the key of to-be-inserted item? Is the comment // Cannot happen because item is not in list correct?
2. The sorted list ADT is to be extended with a Boolean member function, IsThere, which takes as a parameter an item of type ItemType and determines whether there is an element with this key in the list.
a. Write the specification for this function.
b. Write the prototype for this function.
c. Write the function definition using the binary search algorithm.
d. Describe this function in terms of Big-O notation.
3. True/False. If false, justify.
a. Searching sorted and unsorted lists is equally computationally expensive. In both cases, computational complexity is 2^n, Where N is the size of the first element of the list.
b. The order of inserting an element into its place in an unsorted list implemented in an array is O(logN).
4. True/False. If false, justify.
a. There is a major problem with the classes "UnsortedType" and "SortedType" in that the user may accidently overwrite "length", the length of the list, thus changing arbitrarily the list processed.
b. Due to the associated computational expense, the overloading of "InsertItem" goes against the goal of creating an ADT.
## Deliverables
1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.
2) Installation package that will install the software (in ready-to-run condition) on the platform(s) specified in this bid request.
3) Exclusive and complete copyrights to all work purchased. (No GPL, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site).
## Platform
WindowsXP, Windows 2000, Windows 98, and Windows 95