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.
