CODEWITHSUNDEEP
javabig-oinsertion-sort
Wololo
Wololo

Reputation: 861

Finding big-o time complexity of insertion sort

This is how the book calculates Insertions sort's time complexity:

Let T(n) denote the complexity for insertion sort and c denote the total number of other operations such as assignments and additional comparisons in each iteration. Thus,

T(n) = (2 + c) + (2 * 2 + c) + . . . + (2 * (n - 1) + c)   --->  (1)

     = 2(1 + 2 + . . . + n - 1) + c(n - 1)   --->  (2)

     = 2((n - 1)n/2) + cn - c = n2 - n + cn - c   --->  (3)

     = O(n2)   --->  (4)

I can't understand the first step. Where is this '2' in every term coming from.

Please keep the explanation as simple as possible (Mathematics gives a hard time).

Algorithm:

public class InsertionSort {
/** The method for sorting the numbers */
  public static void insertionSort(double[] list) {
    for (int i = 1; i < list.length; i++) {
    /** insert list[i] into a sorted sublist list[0..i-1] so that
       list[0..i] is sorted. */
       double currentElement = list[i];
       int k;
       for (k = i - 1; k >= 0 && list[k] > currentElement; k--) {
         list[k + 1] = list[k];
       }

       // Insert the current element into list[k+1]
       list[k + 1] = currentElement;
    }
  }
}

Upvotes: 0

Views: 976

Answers (1)

CRC
CRC

Reputation: 185

The 2 is a possible definition. The processing of the alghorithm is divided in something like steps. You could say he uses one step to calculate the comparison in for loop and one step to assign the value.

Moreover you see that you have a nested loop. So for better reading I name the outter loop i-loop and the inner loop j_i-loop. The time to process the j_i-loop is 2 * (i -1). The time to process the i-loop is the time to process (j_1-loop +c)+(j_2-loop +c)+...+(j_n-loop+c).

Now you get the term in first line.

Upvotes: 1

Related Questions