Space Time Complexity with Binary Search

• The relationship between binary and space-time complexity can be demonstrated through an algorithm that performs a binary search.

The relationship between binary and space-time complexity can be demonstrated through an algorithm that performs a binary search.

arr = [1,4,5,7,10,14,42,84,100,134,144,149]

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid
    return -1

binary_search(arr, 84)

7

Reflection: The key to the time and space complexity of the algorithm is the line that calculates the mid value. This line uses bitwise shifting to perform integer division by 2, which is an efficient way to divide by a power of 2. This operation takes O(1) time and space complexity. Overall, the binary search algorithm has a time complexity of O(log n) and a space complexity of O(log n), making it an efficient algorithm for searching sorted lists.