Question

Given a sorted array A of size n, we want to find if an element k belongs to this array. What will be the best time complexity to perform this search operation?

1) O(1)
2) O(log n)
3) O(n)
4) O(n²)

Answer 1

The best time complexity to perform this search operation is O(log n) using a binary search algorithm on a sorted array.

Step-by-step explanation:

The best time complexity to perform this search operation is O(log n), where n represents the size of the array.

This is because a binary search algorithm can be used on the sorted array to find the element k. A binary search repeatedly divides the search space in half, narrowing down the possible locations of the target element until it is found or determined to not be present. As a result, the time complexity of a binary search is logarithmic.

For example, if the array has 100 elements, a binary search would take at most 7 comparisons to determine if an element is present, whereas a linear search would take at most 100 comparisons.