Provide best-case and worst-case running time and space complexity analysis in B

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.

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;

       }

}

Explanation / Answer

/* the provided code is of insertion sort. In the insertion sort we start from the second element to the end of the array ( outer loop ). And then we create the inner loop from from i to 0.

In insertion sort we take an element from the outer loop and check whether this element is smaller than the elements in the inner loop , we find that then we swap the element.

The best case complexity of insertion sort will be 0(n). The insertion sort provides the best case complexity when array is already sorted.

For example let's take array is

1,2,3,4,5

So I will move from index 1 to 5

So first iteration

I = 1 and j = 1

It compares a[j-1] and a[j] i.e. 2 and 1 and 2 < 1 is false so it doesn't go to inner loop so no swapping.

Second iteration

i = 2 and j = 2

So it compares 3 < 2 is false so doesn't go to loop

Similarly third iteration i = 3 and j = 3

It compares 4 < 3 which is false doesn't go to inner loop

Similarly fourth iteration

It compares 5< 4 which is false so doesn't go to inner loop.

So if you analyse it you will find that when the array is already sorted then the it doesn't go to inner loop at all because it finds the condition isLessThan(a[j], a[j-1]) false.

So it traverses only outer loop so complexity will be O(n) only and as we have not used any extra space so space complexity will be O(1).

Similarly let's consider the worst case complexity.

The worst case complexity will be when array is sorted in decreasing order i.e.

5, 4 ,3, 2, 1

So in this case for each element the inner loop gets executed

First iteration

i = 1 and j = 1

So compare a[ j] and a[ j-1] i.e 4 and 5 and 4 < 5 is true

So it goes into inner loop and swaps 4 and 5

So array becomes 4, 5 , 3, 2, 1

Second iteration

i = 2 and j = 2 and 3 < 5 so swap and then 3< 4 so swap

So array will become 3, 4, 5, 2, 1

Third iteration

i = 3 and j= 3 and 2 < 5 so swap then 2< 4 so swap and 2< 3 swap

So array will become

2, 3, 4, 5,1

Fourth iteration

i = 4 and j = 4 , 1< 5 so swap, 1< 4 so swap, 1< 3 so swap, 1< 2 so swap so array will become

1, 2, 3, 4, 5

So in worst case when the array is sorted in decreasing order , for each element in the outer loop we are comparing with inner loop elements and swapping it.

So total complexity will be O( n2) and as we haven't used any extra space so space complexity will be O(1).

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.