Computer Sciences > GATE 2025 SET-2 > Searching
An array A of length n with distinct elements is said to be bitonic if there is an index 1≤i≤n such that A[1..i] is sorted in the non-decreasing order and A[i+1..n] is sorted in the non-increasing order.
Which ONE of the following represents the best possible asymptotic bound for the worst-case number of comparisons by an algorithm that searches for an element in a bitonic array A?
Which ONE of the following represents the best possible asymptotic bound for the worst-case number of comparisons by an algorithm that searches for an element in a bitonic array A?
Explanation
Correct : d
Similar Questions
What is the worst-case time complexity of insertion in an AVL tree?
Which operations on a binary search tree have O(h) complexity?
Compare search complexities of sorted array vs balanced BST.