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]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?
Solution :
The correct option is Θ(log n).
Let us understand why the worst-case number of comparisons for searching an element in a bitonic array is bounded by .
A bitonic array is an array that consists of distinct elements, which first increases monotonically up to a certain maximum element (the peak element at index ), and then decreases monotonically. Formally, is sorted in ascending order and is sorted in descending order.
To search for a target element in such an array efficiently, we can break down the process into two main phases, both utilizing modified binary search:
Step 1: Finding the peak element (the bitonic point)
We can find the index of the peak element using a modified binary search. At each step, we look at the middle element and compare it with its neighbors:
- If and , then is the peak.
- If and , the peak must lie in the right half: .
- If and , the peak must lie in the left half: .
Since we halve the search space at each step, finding the peak element takes comparisons.
Step 2: Searching for the target element
Once the peak index is identified, the array is split into two sorted subarrays:
1. An ascending sorted subarray .
2. A descending sorted subarray .
We perform a standard binary search for the target element on the ascending subarray, which takes comparisons. If not found, we perform a binary search (adapted for descending order) on the descending subarray, which takes comparisons.
Total Time Complexity:
The overall worst-case comparisons is the sum of the comparisons in both steps:
Since and , the complexity simplifies to:
Thus, the best possible asymptotic bound for the worst-case number of comparisons is .
Completely free for students. Educators & coaching institutes get 2 months free Pro trial to create tests.
Access unlimited practice questions, detailed step-by-step solutions, and exam study materials — completely free for students.
Create and conduct professional online assessments with AI question generation, tab proctoring, and comprehensive batch management.
A comprehensive CUET UG Mathematics Question Paper with Solutions – 2 June 2023 (Shift 3) designed to help students practice and understand the actual CUET exam pattern. This paper covers important topics from Algebra, Calculus, Coordinate Geometry, Probability, Statistics, Matrices, Determinants, and Vectors, featuring a balanced mix of conceptual, numerical, and application-based questions. Detailed solutions are provided to strengthen problem-solving skills, improve conceptual clarity, and enhance calculation accuracy. Based on the CUET syllabus and previous year exam trends, this paper is ideal for practice, revision, self-assessment, time management, previous year analysis, and final preparation for upcoming CUET UG Mathematics examinations.
A comprehensive CUET Accountancy Question Paper – 20 June 2023 (Shift 2) designed to help students practice and analyze previous year exam patterns for effective CUET preparation. This paper covers important topics including Accounting for Partnership Firms, Company Accounts, Financial Statements Analysis, Cash Flow Statements, Accounting Ratios, and Fundamental Accounting Principles. It features a balanced mix of conceptual, numerical, and application-based questions to strengthen accounting concepts, improve calculation accuracy, and enhance problem-solving skills. Based on the CUET exam structure and syllabus, this paper is ideal for practice, revision, self-assessment, time management, previous year analysis, and final preparation for upcoming CUET Accountancy examinations.
Copyright © 2026 Combe Labs Private Limited. All Rights Reserved.