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 binary search algorithm is analyzed in a case where the item to be searched is assumed to be NOT found in the sorted array (i.e. Worst Case Analysis). // Worst Case Analysis (e.g., item not in array) int binarySearch(item, sortedArray) { // Instruction Count int low = 0; // 1 int high = sortedArray.length - 1; // 1 int mid = 0; // 1 while (low <= high) { // ≈ log(n) + 1 mid = (low + high) / 2; // ≈ log(n) if (sortedArray[mid] == item) { // ≈ log(n) return mid; } else { if (sortedArray[mid] < item) { // <─┐ low = mid + 1; // │ } else { // ├─> ≈ 2 * log(n) high = mid - 1; // │ } // <─┘ } } return -1; // 1 } // --------------
Complete the following analysis of an
// Worst Case Analysis (e.g., item not in array)
int binarySearch(item, sortedArray) { // Instruction Count
int low = 0; // 1
int high = sortedArray.length - 1; // 1
int mid = 0; // 1
while (low <= high) { // ≈ log(n) + 1
mid = (low + high) / 2; // ≈ log(n)
if (sortedArray[mid] == item) { // ≈ log(n)
return mid;
} else {
if (sortedArray[mid] < item) { // <─┐
low = mid + 1; // │
} else { // ├─> ≈ 2 * log(n)
high = mid - 1; // │
} // <─┘
}
}
return -1; // 1
} // --------------
Step by step
Solved in 2 steps