Analysis of Linear Search
To look at how to perform analysis, we will start with a performance analysis of the following C++ function for a linear search:
Assumptions
Looking at this code, we can see that there is a loop. The loop stops on one of two conditions, it reaches the end of the array or rc becomes something other than -1. rc changes only if key is found in the array. So, what are the possibilities when I run this program?
1) key is not in the array... in that case loop stops when it gets to the end of the array
2) key is in the array... but where? If it is at the front, then loop stops right away, if it is in the back then it needs to go through all the elements... clearly these will both affect how many operations we carry out.
The worst case scenario is that of an unsuccessful search... the loop will need to run more times for that. If the search was successful however, where will the key be? To perform an average case scenario, we need to consider the likelihood of finding the key in each element. Now, making the assumption that the key is equally likely to be in any element of the array, we should expect to go through half the array on average to find key.
We will look at each of these in turn below
Analysis of an Unsuccessful Search
Let n represent the size of the array arr. Let T(n) represent the number of operations necessary to perform linear search on an array of n items.
Next we go through the code and count how many operations are done. We can do this by simply adding a comment to each line with the total operation count per line. That is we count how many operations are on that line AND the number of times that particularly line is done.
In the above code we are treating arr.size() function call as if its a constant value or variable. This can be done only because the size() function in vector class is constant. You can check this out here: https://en.cppreference.com/w/cpp/container/vector/size under the heading complexity. If the complexity was something else, we would need to account for this in the analysis. For example, strlen() in cstring library does not have a constant run time and thus we can't count it as one operation
Where do the counts come from?
int rc=-1;
is only ever done once per function call, there is one operator on that line, so the count is 1for(int i=0;i<arr.size()&& rc==-1;i++)
int i=0 is only done once per function call, so it is counted as 1, the other operations <, . (dot), &&, == and ++ happen for each loop iterations and since the loop happens n times, each of those 5 operations are multiplied by nif(arr[i]==key)
this is done every time we are in loop, loop runs n times, so count as 1rc=i
it is worth noting that because we are assuming our search is unsuccessful, the if statement never evaluates to true, thus, this line of code never runs. Thus, it is not countedreturn rc;
like the first initialization statement this return statement only happens once, so we count it as 1
Come up with the expression for T(n)
Recall that T(n) represents the total number of operations needed for an unsuccessful linear search. As such, we get T(n) by summing up the number of operations. Thus:
\begin{align*} T(n) &= 1 + 1 + 5n + n + 1 \\ &= 6n + 3 \end{align*}
Thus the expression for the nu-mber of operations that is performed is:
Now... can we actually prove this?
According to the formal definition for big-O
This is also the reason why it did not matter if we counted the operations for the . operator or the [i] operator. If we counted both of them,
The dominating term would be 8n but this is still O(n).
Analysis of a Successful Search
In the previous analysis, we assumed we wouldn't find the data and thus the worst possible case of searching through the entire array was used to do the analysis. However, what if the item was in the array?
Now since we will at some point find the item, the statement inside the if will also be performed. Thus, we will have 4 operations that we must run through once.
These other operations will also run for each iteration of the loop:
The difference is we do not expect that the loop would have to run through the entire array. On average we can say that it will go through half of the array.
Thus:
Last updated