Question

Given an array \( A[n] \) such that:

\[ A[0] \to A[i] \text{ is in non-decreasing order}, \quad A[i+1] \to A[n] \text{ is in non-increasing order}. \]

Find the time complexity to find \( A[i] \).

• A. \( O(N) \)
• B. \( O(\log_2 N) \)
• C. \( O(\log n \times \log n) \)
• D. \( O(1) \)

Hint:

In problems involving ordered subarrays, using binary search can reduce the time complexity significantly, especially when searching in logarithmic time.

Answer 1

The Correct Option is C

Step 1: Understanding the problem.

The array is divided into two parts:
- The first part from \( A[0] \) to \( A[i] \) is in non-decreasing order.
- The second part from \( A[i+1] \) to \( A[n] \) is in non-increasing order.


To find the correct index \( i \), we need to identify the point where the non-decreasing sequence ends and the non-increasing sequence begins.

Step 2: Using binary search.

We can apply binary search to both halves of the array:
- Perform binary search to find the boundary between the non-decreasing and non-increasing parts.

Since binary search operates in \( O(\log n) \) time, and we perform binary search on both parts of the array, the total time complexity becomes: \[ O(\log n) \times O(\log n) = O(\log n \times \log n) \]

Thus, the correct answer is \( O(\log n \times \log n) \).