Question

def binsearch(a):
    if len(a) == 1:
        return a[0]
    else:
        mid = len(a)//2
        min1 = binsearch(a[0:mid])
        min2 = binsearch(a[mid:len(a)])
        if min1 < min2:
            return min1
        else:
            return min2

What is the time complexity for the function? include derivative steps to your answer

Answer 1

The time complexity for the given function is O(log n).

def binsearch(a):       // Function definition
    if len(a) == 1:       // Condition checking, will take constant time
        return a[0]      // Return value, will take constant time
    else:                   // When the if condition fails
        mid = len(a)//2          // Dividing the array into two halves
        min1 = binsearch(a[0:mid])      // Applying binary search on the first array
        min2 = binsearch(a[mid:len(a)])    // Applying binary search on the second array
        if min1 < min2:                  // Condition checking
            return min1                   // Return value
        else:                               // Else part of the condition
            return min2            // Return value

In this approach the entire search space is divided into two equal lengths array. The binary search operation is performed on each of them at every step. The first search runs from the beginning to the middle of the array and the second search runs from the middle to the end of the array. In every iteration the length of the array is divided into two equal length sub-arrays which are again getting divided. So, the total time taken will be equivalent to the logarithm of the input array, which is O(log n).

Please comment in case of any doubt.
Please upvote if this helps.