Find Minimum in Rotated Sorted Array in DSA C++ - Time & Space Complexity

Time Complexity: Find Minimum in Rotated Sorted Array

O(log n)

Understanding Time Complexity

We want to understand how fast we can find the smallest number in a rotated sorted array.

How does the time needed change as the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int findMin(const std::vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
}
    

This code finds the minimum element by using a binary search approach on a rotated sorted array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that halves the search range each time.
• How many times: The loop runs until the search space is reduced to one element, about log base 2 of n times.

How Execution Grows With Input

Each step cuts the array roughly in half, so the number of steps grows slowly as the array grows.

Input Size (n)	Approx. Operations
10	About 4 steps
100	About 7 steps
1000	About 10 steps

Pattern observation: Doubling the input size adds only one more step, showing slow growth.

Final Time Complexity

Time Complexity: O(log n)

This means the time to find the minimum grows slowly, even if the array becomes very large.

Common Mistake

[X] Wrong: "Since the array is rotated, we must check every element to find the minimum, so it takes O(n) time."

[OK] Correct: The binary search approach uses the sorted property cleverly to skip half the elements each time, so it does not need to check all elements.

Interview Connect

Understanding this pattern helps you show how to use binary search in clever ways beyond simple sorted arrays, a skill valued in problem solving.

Self-Check

"What if the array was not rotated but still sorted? How would the time complexity change?"