Find Minimum in Rotated Sorted Array in DSA Javascript - 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 list.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function findMin(nums) {
  let left = 0;
  let right = nums.length - 1;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return nums[left];
}
    

This code finds the smallest number in a rotated sorted array by using a smart search that cuts the search space in half each time.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that compares middle and right elements to narrow down the search.
• How many times: The loop runs until the search space is reduced to one element, roughly halving each time.

How Execution Grows With Input

Each step cuts the list roughly in half, so the number of steps grows slowly even if the list grows a lot.

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

Pattern observation: The steps grow very slowly compared to input size because the search space halves each time.

Final Time Complexity

Time Complexity: O(log n)

This means the time to find the minimum grows slowly as the list gets bigger, making it very efficient.

Common Mistake

[X] Wrong: "The search must check every number to find the minimum, so it takes O(n) time."

[OK] Correct: The code uses a smart method that cuts the search area in half each time, so it doesn't check every number.

Interview Connect

Understanding this search method shows you can use smart ways to find answers quickly, a skill that helps in many coding problems.

Self-Check

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