Provide best-case and worst-case running time and space complexity analysis in B
ID: 3748565 • Letter: P
Question
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 <T extends Comparable<T>> 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 static<T extends Comparable<T>> boolean isLessThan(T v, T w) {
return v.compareTo(w) < 0;
}
public static<T> void swap(T[] a, int i, int j) {
T t = a[i];
a[i] = a[j];
a[j] = t;
}
}
Big-O Notation
Example Input
Explanation
Best-Case Running Time
Worst-Case Running Time
Best-Case Space Complexity
Worst-Case Space Complexity
Explanation / Answer
Big-O Notation
Example Input
Explanation
Best-Case Running Time
Worst-Case Running Time
Best-Case Space Complexity
Worst-Case Space Complexity
Big-O Notation
Example Input
Explanation
Best-Case Running Time
O(n) [1,2,3,4,5] Given an Array which is already Sorted in Increasing Order. The second for loop will not be satisfied because 2 > 1, 3>2, 4>3 and 5>4.Hence only the first for loop will run through all element resulting in O(n)
Worst-Case Running Time
O(n2) [5,4,3,2,1] Given an Array which is already Sorted in decreasing Order. The second for loop need to run 1 , 2, 3, 4, ..n-1 times for each iThus if we sum over all the i's we will get 1 + 2 + 3+ 4 + ..n ..resulting in n*(n+1)/2
Best-Case Space Complexity
O(n) [1,2,3,4,5] Given an Array which is already Sorted in Increasing Order. The second for loop will not be satisfied because 2 > 1, 3>2, 4>3 and 5>4.Hence only the first for loop will run through all element resulting in O(n)
Worst-Case Space Complexity
O(n2) [5,4,3,2,1] Given an Array which is already Sorted in decreasing Order. The second for loop need to run 1 , 2, 3, 4, ..n-1 times for each iThus if we sum over all the i's we will get 1 + 2 + 3+ 4 + ..n ..resulting in n*(n+1)/2
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.