Problem
I. John was a student who enjoyed implementing and testing visas in class. He that well the sort Insertion was efficient for several elements. He then implemented the following:
JOHN-ALGORITHM (v, n):
if n ≤ 100
then INSERTIONSORT(v, n)
else MERGESORT(v, n)
Peter, a colleague of John's, knew that Insertion sort had O(n2) worst-case complexity and concluded that John's algorithm had O(n2) complexity. John, on the other hand, claimed that his algorithm had O(n log n) complexity. Who is right? Why?
II. Consider an ordered vector v with n distinct integers. Create an algorithm with O(log n) complexity to determine if there is an index i such that v[i] = i.
III. Design an algorithm to determine whether two sets A and B are disjoint (have no elements in common). Being |A| = n and |B| = m, describe the complexity of your algorithm in terms of n and m.
IV. It is possible to create a solution to the previous exercise in the order of O(n log n) or O(n log m). Describe this solution.
V. Quicksort runtime for a sequence with 1024 elements takes an average of 100 ms. What is the running time, on average, if the sequence size were 8192? Justify your answer.