Machine Independent Worst Case Time Complexity Analysis Linear Search

Machine Independent Worst Case Time Complexity Analysis Linear Search:

Linear Search C Code:

/*c1*/ found = 0;

/**
 * What if the input size was (n) instead of 6
 */
for (/*c2*/ i = 0; /*c3*/ i < 6; /*c7*/ ++i){
     /*c4*/     if (A[i] == key){
     /*c5*/         found = i;
     /*c6*/          break;
                }
}

/*c8 */ if (found)
/*c9 */    printf("Found at %d\n", i);
/*c10*/ else
           printf("Not found");

Analysis:

Let, c1, c2, c3… be micro instructions for a particular command. Let input size, n = 6.

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

Explanation:

Our input instance size was 6. Here (c1) always executes only once. So does (c2) when initializing the for loop condition. But the for loop condition (c3) executes 7 times. Our for loop counter is initialized to 0.

For 0 its checks condition once. Finds 0 < 6 true continues loop.
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.

The loop condition (c3) is checked 7 times (n+1) but it enters the loop 6 times (n). So for this algorithm if the input size is (n) the condition will be checked (n+1) times. The last check 6 < 6 is false. So it doesn’t enter the loop.

Inside the loop in any case (c4) is always executed. In the event of worst case (c4) is true every time (n), then two more micro instructions are executed (c5), (c6).

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

(C8) is always executed once. Then based on the truth value of (c8) either (c9) or (c10) is executed once.


So we can write,

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

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

     = c1 + c2 + c3 + 7*c3 + 6*c4 + 6*c5 + 6*c6 + 6*c7 + c8 + c9

     = c1 + c2 + c3 + (n+1)*c3 + n*c4 + n*c5 + n*c6 + n*c7 + c8 + c9   [substituting 6 with n]

     = c1 + c2 + c3 + c3 + n*c3 + n*c4 + n*c5 + n*c6 + n*c7 + c8 + c9

     = c1 + c2 + c3 + c3 + n*c3 + n*c4 + n*c5 + n*c6 + n*c7 + c8 + c9  [rearranging constants]

     = ( c1 + c2 + 2*c3 + c8 + c9 ) + n * ( c3 + c4 + c5 + c6 + c7 )

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

     = an + b

     = O(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 O(n). Also known as order, Big O.

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