Question

Given a sorted array, what can be the minimum worst-case time complexity to find the ceiling of a number x in a given array? The ceiling of an element x is the smallest element present in the array, greater than or equal to x. The ceiling is not present if x is greater than the maximum element present in the array. For example, if the given array is 12, 67, 90, 100, 300, 300, and x = 95, then the output should be 100.

Options:

i. O(n)

ii. O(√n)

iii. O(log(logn))

iv. O(logn)

Answer 1

The minimum worst-case time complexity to find the ceiling of a number x in a sorted array is O(logn), using a binary search algorithm.

Step-by-step explanation:

To find the ceiling of a number x in a given sorted array, the algorithm with the minimum worst-case time complexity that can be used is a binary search. A binary search approach, which splits the array into halves to locate an element, has a time complexity of O(logn). So, the correct answer to the question is O(logn).

In the given example with x = 95, starting the search mid-way through the array and repeatedly halving the search interval allows us to quickly narrow down to the elements around 95. Since the array is sorted, once we find an element that is greater than or equal to 95, we've located the ceiling. If x is greater than the maximum element in the array, we can also quickly determine that there is no ceiling present in the array.