Count Occurrences of Element in Sorted Array in DSA Javascript - Time & Space Complexity

Time Complexity: Count Occurrences of Element in Sorted Array

O(log n)

Understanding Time Complexity

We want to know how fast we can count how many times a number appears in a sorted list.

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function countOccurrences(arr, target) {
  function findFirst() {
    let left = 0, right = arr.length - 1;
    while (left <= right) {
      let mid = Math.floor((left + right) / 2);
      if (arr[mid] < target) left = mid + 1;
      else right = mid - 1;
    }
    return left;
  }

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

  const first = findFirst();
  const last = findLast();
  if (first > last) return 0;
  return last - first + 1;
}

This code finds the first and last positions of the target number using binary search, then calculates how many times it appears.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two binary search loops that repeatedly cut the search range in half.
• How many times: Each binary search runs about log₂(n) times, where n is the array size.

How Execution Grows With Input

Each binary search cuts the search space in half each step, so the number of steps grows slowly as the list grows.

Input Size (n)	Approx. Operations (per binary search)
10	About 4
100	About 7
1000	About 10

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

Final Time Complexity

Time Complexity: O(log n)

This means the time to count occurrences grows slowly, even if the list gets very large.

Common Mistake

[X] Wrong: "Counting occurrences requires checking every element, so it must be O(n)."

[OK] Correct: Because the array is sorted, we can use binary search to jump directly to the first and last positions, avoiding checking every element.

Interview Connect

Knowing how to use binary search to count occurrences shows you understand how to use sorting to speed up searching, a key skill in many coding challenges.

Self-Check

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