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

Time Complexity: Find Minimum in Rotated Sorted Array

O(log n)

Understanding Time Complexity

We want to know 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.

func findMin(nums []int) int {
    left, right := 0, len(nums)-1
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] > nums[right] {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return nums[left]
}

This code finds the minimum value 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 loop that halves the search range each time.
• How many times: The loop runs until the search range is reduced to one element, about log base 2 of n times.

How Execution Grows With Input

Each time the array size doubles, the number of steps increases by one.

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

Pattern observation: The steps grow slowly as input size grows, increasing by one each time the input doubles.

Final Time Complexity

Time Complexity: O(log n)

This means the time to find the minimum grows slowly, adding only a few extra steps even if the array gets much bigger.

Common Mistake

[X] Wrong: "The loop runs through every element, so it is O(n)."

[OK] Correct: The code cuts the search space in half each time, so it does not check every element one by one.

Interview Connect

Understanding this time complexity shows you can use efficient search methods on special arrays, a skill often valued in problem solving.

Self-Check

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