Question 24 If a sorted array is rotated by k positions, what is the time complexity to...
Palo Alto Networks technical mcq question, verified with a worked answer. Free to practise - no sign-up.
If a sorted array is rotated by k positions, what is the time complexity to find the starting point of the original array?
Select any one of the following options
Show answer & explanation
Answer: A. A) O(logn)
Using modified binary search, the minimum element (inflection point where rotation occurs) can be found in O(log n) time.
Step-by-step Derivation:
Step 1: A rotated sorted array has two sorted subarrays.
Step 2: By comparing the middle element with the high element, we can determine which half contains the pivot point.
Step 3: The search range is halved in each step, taking O(log n) time.