We have the following array 1 34 56 78 99 123 234 a. What is the big Oh notation

Question

We have the following array 1 34 56 78 99 123 234

a. What is the big Oh notation of the Time Complexity of using the Sequential search algorithm to find a number in this array ? b. Assuming each loop iteration of the Sequential search algorithm takes 0.5 ms, how long does it take for the sequential search algorithm to find (or try to find) the integer: 56 ? 78 ? 100 ? Explain your answers c. What is the big Oh notation of the Time Complexity of using the Binary search algorithm to find a number in this array ? d. How many division (loop iteration) in the Binary search algorithm are required to find (or try to find) the integer: 56 ? 78 ? 100 ? Explain your answers

Explanation / Answer

We have the following array 1 34 56 78 99 123 234
a. What is the big Oh notation of the Time Complexity of using the Sequential search
   algorithm to find a number in this array ?
Sequential search also called brute-force search is a search method which doesn't involves
much of a technique, and will just keep searching for the key element from the first element
i.e., the element at index 0, and will go till either the element is found, or end of array
is reached thereby concluding that the element is not found.
So, in the best case this search takes just one comparison, which happens when the search
key is the first element of the array itself.
But in the worst case it takes a total of n comparisons as it will exhaustively search
from start of the array and will proceed throughout the array. And therefore the efficiency is O(n).

b. Assuming each loop iteration of the Sequential search algorithm takes 0.5 ms, how long
   does it take for the sequential search algorithm to find (or try to find) the
   integer: 56 ? 78 ? 100 ? Explain your answers
   So, to search for 56 it has to compare a total of 3 elements in the array, 1, 36, and 56.
   So, the time required to search for 56 is: 0.5 * 3 = 1.5 ms.
   To search for 78 it has to compare a total of 4 elements in the array, 1, 36, 56, 78.
   So, the time required to search for 78 is: 0.5 * 4 = 2 ms.
   To search for 100 it has to loop through all the elements in the array.
   So, the time required to search for 100 is: 0.5 * 7 = 3.5 ms.
  
c. What is the big Oh notation of the Time Complexity of using the Binary search
   algorithm to find a number in this array ?
Binary search has a pre-requisite before it could happen. It is the list should be readily
sorted unless otherwise this technique could not be applied. And now, everytime a mid
value is calculated such that low value is the index of the left most element of the array,
and high value is the index of the right most element in the array. And mid value is
calculated using the formula: mid = (low + high) / 2;
Now, this mid indexed element is compared with key.
There are 3 possibilities as the list is readily sorted.
My search key is at index mid. (if key == array[mid]). So, element is found and return.
My search key could be on left side of the mid. (if key < array[mid]). So, update high
   to mid - 1.
My search key could be on the right side of the mid. (if key > array[mid]) So,
   update low to mid + 1.
And this process continues till the element is found, or the list gets exhausted, i.e.,
the low value goes higher than high.
In this technique the size of array is being halved at each step and therefore, the
efficiency of this algorithm is O(log n.)  

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.