Insertion Sort Best Case Time Complexity Analysis

Insertion Sort Best Case Time Complexity Analysis:

Insertion Sort Code:

for (/*c1*/ i = 1; /*c2*/ i < n; /*c3*/ ++i){
     /*c4*/ key = A[i];
     /*c5*/ j = i - 1;
     /*c6*/ while (j >= 0 && key < A[j]){
        /*c7*/ A[j+1] = A[j];
        /*c8*/ --j;
    }
    /*c9*/ A[j+1] = key;
}

Analysis:

Let, c1, c2, c3… be micro instructions for a particular command. Let input size, n = 6. Now setting n = 6 in the code above we find this relation below.

Micro Instructions    Times (Number of times it was executed)
==================    =======================================
              c1 -----> 1
              c2 -----> 6 -----> ( n )
              c3 -----> 5 -----> ( n - 1 )
              c4 -----> 5 -----> ( n - 1 )
              c5 -----> 5 -----> ( n - 1 )
              c6 -----> 5 -----> ( n - 1 )
              c7 -----> 0
              c8 -----> 0
              c9 -----> 5 -----> ( n - 1 )

Explanation:

Our input instance size was 6. Here (c1) always executes only once. But the for loop condition (c3) executes 6 times since our for loop counter is initialized to 1 instead of 0.

For 1 its checks condition once. Finds 1 < 6 true continues loop.
For 2 its checks condition once. Finds 2 < 6 true continues loop.
For 3 its checks condition once. Finds 3 < 6 true continues loop.
For 4 its checks condition once. Finds 4 < 6 true continues loop.
For 5 its checks condition once. Finds 5 < 6 true continues loop.
For 6 its checks condition once. Finds 6 < 6 false exits the loop.

Since the loop counter begins at 1 so condition is checked from 1 to n times. For the nth time even though it results in false but condition is executed to get that false result. The loop condition (c2) is checked 6 times (n) but it enters the loop 5 times (n-1). So for this algorithm if the input size is (n) the condition will be checked (n) times. The last check 6 < 6 is false. So it breaks the loop.

Inside the loop in any case (c4, c5, c6, c9) is always executed in the best case. But in the event of best case the while loop condition becomes false. So instructions inside while loop ( c7, c8 ) are never executed. For this reason we have a faster runtime.

For insertion sort the best case is input is already sorted in the desired order. So it never enters the while loop since key is never less/greater ( depending on ascending or descending order sort ) than its previous elements.

The loop increment is executed (n – 1) times because when it enters the loop for the first time the increment is not executed.


So we can write,

T(n) = summation of micro instructions * number of times executed

T(6) = c1 + n*c2 + (n-1)*c3 + (n-1)*c4 + (n-1)*c5 + (n-1)*c6 + 0*c7 + 0*c8 + (n-1)*c9

     = (c1 - c2 - c3 - c4 - c5 - c6 - c9) + n * (c2 + c3 + c4 +c5 + c6 + c9)  [multiplying and rearranging constants]

     = b + n * a  [ Let, sum of constants, c1 - c2 - c3 - c4 - c5 - c6 - c9 = b, c2 + c3 + c4 +c5 + c6 + c9 = a ]

     = an + b

     = Ω(n)

Lower Bound,

We represent asymptotic lower bounds with big – Ω ( Big Omega ) notation. So the lower bound for insertion sort is Big Omega of n.

Ω(n)


Now,

T(n) = an + b

we know,
y = mx + c
f(x) = mx + c

From this we can see these equations are similar and our equation matches linear equation. If we plot the graph of an+b for different values of n we will see that it is a straight line. So for any value of n it will give us linear time. Even as input size gets very large our time complexity will always be linear. So, we can write this as Ω(n). Also known as Big Omega.

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s