Question

What is the Big-Oh notation of the following code snippet:

BinarySearch(numbers, N, key) {

    mid = 0;

   low = 0;

   high = 0;

   high = N - 1;

   while (high >= low) {

      mid = (high + low) / 2

      if (numbers[mid] < key) {

         low = mid + 1

      }

      else if (numbers[mid] > key) {

         high = mid - 1

      }

      else {

         return mid

      }

   }

   return -1   // not found
}

Answer 1

Big-oh notation means the worst case complexity. The code snippet we are inspecting is a binary search algorithm.

The worst case complexity of binary search is log₂N where N is the number of elements. It occurs when the search key is located at first or last index of the list.

Let's take an example:

List = 1, 2, 3, 4, 5, 6, 7, 8, 9

N = 9

if key = 1:

then, first pass:

mid = (8+0)/2 = 4, list[mid] is 5, and 1 is less than 5 so high becomes 4-1=3, in second pass:

mid = (3+0)/2 = 1,list[mid] is 2, and 1 is less than 2 so high becomes 1-1 = 0, in third pass:

mid = (0+0)/2 = 0, list[mid] is 1 and key is also 1.

So search is completed after 3 passes. 3 comparisons are required.

Now let's calculate log₂9 = 3.16 which is approximately 3.

So our example satisfies Big-oh.

Note : mid value is calculated as integer that's why only the value before decimal point.

You can further test your code with other lists and extreme values. Add a count variable in your code and see the count results for different combinations. You will always find that O(log₂N ) for this code.

If you have any query then ask me in comment section. Please give a thumbs up if you find the answer helpful.