Complete the following analysis of an algorithm such that the time complexity, T(n), of the given algorithm is determined. The analysis uses instruction count (i.e. number of times the statement is executed) as the measure for the analysis. The instruction count of each instruction in the algorithm is indicated at the right of the statement after the //. You should replace each of the question marks(?) by the corresponding instruction count in order to complete the analysis. The total instruction count is obtained by adding all the instruction counts. Note that in this exercise, the linear search algorithm is analyzed in a case where the item to be searched is assumed not found in the array (i.e.Worst Case Analysis) int linearSearch(item, array) { // worst case instruction count int index = 0; // ? while (index < array.length) { // ? if (array[index] == item) { // ? return index; // ? } index++; // ? } return -1; // ? } // ------ // T(n) = ? where n is the array size
Complete the following analysis of an
int linearSearch(item, array) { // worst case instruction count
int index = 0; // ?
while (index < array.length) { // ?
if (array[index] == item) { // ?
return index; // ?
}
index++; // ?
}
return -1; // ?
} // ------
// T(n) = ? where n is the array size
Step by step
Solved in 3 steps
