Provide best-case and worst-case running time and space complexity analysis in Big-Oh notation for the following sort method. For each case, provide an example input array and brief explanation.

	Big-O Notation	Example Input	Explanation
Best-Case Running Time
Worst-Case Running Time
Best-Case Space Complexity
Worst-Case Space Complexity

public class InsertionSort {

/**

* Sort the input array into non-decreasing order

* @param a Input array, assume not null

*/

public static extends Comparable> void sort(T[] a) {

int n = a.length;

for (int i = 1; i < n; i++) {

// Insert a[i] into sorted section: 0, 1, ..., a[i-1]

for (int j = i; j > 0 && isLessThan(a[j], a[j - 1]); j--) {

swap(a, j, j - 1);

}

}

}

public staticextends Comparable> boolean isLessThan(T v, T w) {

return v.compareTo(w) < 0;

}

public static void swap(T[] a, int i, int j) {

T t = a[i];

a[i] = a[j];

a[j] = t;

}

}