In java and for the methods belows analyze the run-time performance address the following:

1. What is the Big-O behavior and why? Be sure to define N.

2. Plot the running time for various problem sizes .

3. Does the growth rate of the plotted running times match the Big-O behavior you predicted?

4. How do these methods compare to using java's insertion sort?

public static void insertionSort(T[] typeList, Comparator comp) throws NullPointerException {

if (typeList == null || comp == null) {

throw new NullPointerException();

}

for (int i = 0; i < typeList.length; i++) {

T holder = typeList[i];

int j = i - 1;

while (j >= 0) {

if (comp.compare(typeList[j], holder) <= 0) {

break;

}

typeList[j + 1] = typeList[j];

j--;

}

typeList[j + 1] = holder;

}

}

public static String[] getLargestAnagramGroup(String[] anagramList) {

String[] anagramCopy = Arrays.copyOf(anagramList, anagramList.length); // We copy the original array, so to have

// the original unsorted Strings.

for (int index = 0; index < anagramList.length; index++) {

anagramList[index] = sort(anagramList[index]); // we sort each word, so that it is in "anagram sorted" form.

}

insertionSort(anagramList, (lhs, rhs) -> lhs.compareTo(rhs)); // sort the list so that the same strings are

// sequential.

int max = 0;

String currentAna = "";

for (int index = 0; index < anagramList.length - 1; index++) {

String comparor = anagramList[index]; // basis for tracking each anagram group

int jindex = index + 1;

int count = 1; // number of anagrams in the group

while (jindex < anagramList.length && comparor.equals(anagramList[jindex])) {

count++;

jindex++;

}

if (count > max) {

max = count;

currentAna = anagramList[index];

}

}

String[] result = new String[max]; // Build a smaller array of the largest group of anagrams.

int indexResult = 0;

for (String ana : anagramCopy) {

if (areAnagrams(currentAna, ana)) {

result[indexResult] = ana;

indexResult++;

}

}

return result;

}