Question

Read the following pseudocode, note that A is a sorted array:
BINARY-SEARCH(A, v)

low := 1

high := n

while low <= high

mid = floor((low+ high)/2)

if v == A[mid]

return mid

else if v > A[mid]

low = mid + 1

else

high = mid - 1

return NIL

a) Find the Recurrence Relation.

b) Is there a tight bound? If the answer is yes, find it.

c) Find the best case and worst case running time.

Answer 1

The given pseudocode is of iterative binary search algorithm, which returns the index of some element that equals the given value(v) in a sorted array (A).
where A: sorted array,
mid: index of middle element of array,
low: 1st element of the array,
hihg: last element of the array,

Now, we first compare the given element (v) with element at middle index of the array. If v matches with middle element i.e. a[mid], then we return middle index(mid). Otherwise, we check the middle element against the key, if it is greater, we check for the first half i.e. left half of array else we check the second half i.e. right half of the array and repeat the same process.

Sol a)
Calculating Recurrence Relation:

• Let say the iteration in Binary Search terminates after k iterations.
• At each iteration, the array is divided by half. So let’s say the length of array at any iteration is n
• At Iteration 1, Length of array = n

• At Iteration 2, Length of array = n⁄2

• At Iteration 3, Length of array = (n⁄2)⁄2 = n⁄22

• Therefore, after Iteration k, Length of array = n⁄2k .

  Also, after k divisions, the length of array becomes 1. Therefore, Length of array = n⁄2k = 1

• Thus, n = 2k
• Applying log function on both sides:
  • => log2 (n) = log2 (2k)
  • => log2 (n) = k log2 (2)
  • => k = log2 (n) (Since loga (a) = 1 )

Hence, the time complexity of Binary Search is log2 (n) or simply put O(log(n))

and Recurrence Relation is : T(n) = T(n/2) + O(1) and T(1) = T(0) = O(1)

Sol b)

Yes, there is a tight bound.

The lower bound for searching in a sorted array using only comparisons is o(log n) and the upper bound complexity is O(log n) (as deducted in sol (a)).

Tight bound (big Theta) takes both upper (big O) and lower bounds (big Omega) into account.
Since, the upper bound and lower bound coincide, O(log n)+O(log n)=O(2log n) and for large values of n, the constants are ignored in Big O notation. So, O(2log n) = O(log n)

Hence, the complexity is: O(log n).

Sol c)

Time Complexity:

• · Best Case: O(1)
• · Average Case: O(logn)
• · Worst Case: T(n)=T(n/2)+c, By using master Theorem O(logn)