BinarySearch is a DivideandConquer algorithm for finding a g

BinarySearch is a Divide-and-Conquer algorithm for finding a given \"key\" in a sorted array (or finding out it does not exist): (or finding out it does not exist): procedure BlNARYSEARCH(A, p, r, key) if p key then return BINARYSEARCH(A, p, q - 1, key) else return BlNARYSEARCH(A, q + 1, r, key) else return NIL Formulate the recurrence that represents the runtime of BlNARYSEARCH. Using Master Method, provide a tight asymptotic bound for the solution of this recurrence. Make sine to specify the Master Theorem case that applies. If we change Line 2 of this procedure to q leftarrow [9(p + r)/10], what would be the runtime of the new algorithm?

Solution

a)
The time complexity of Binary Search can be written as
T(n) = T(n/2) + c

b)
Mater theorem:
   a=1, b=2 c=0 f(n) = c
   logba = 0

   so, loaba = c

   If f(n) = (n^c) where c = Logba then T(n) = (n^cLog n)

   Big-O: O(logn)

c)
   so, in this case we divide array in two parts:
       one part contains n/10 elemnts and other part contains 9n/10

       t(n) = t(n/10)+t(9n/10)+c

       Big-O = O(n)