Discussion
An array \(A\) of length \(n\) with distinct elements is said to be bitonic if there is an index \(1 \le i \le 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\)?
Answer: D
The best bound is Θ(log n).
A search in a bitonic array can be done in three binary searches:
- Find the peak, the index where the array stops increasing: compare A[mid] with A[mid + 1] and move towards the larger one. O(log n) comparisons.
- Binary search the increasing part A[1..peak].
- Binary search the decreasing part with the comparison reversed.
That is O(log n) in all, and Ω(log n) is unavoidable because a sorted array is a special case of a bitonic one, and searching it needs log n comparisons. Θ(n) is a linear scan, Θ(1) is impossible, and Θ(log2 n) is what one gets by searching without first finding the peak, which is not optimal.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development