Count Occurrences of Element in Sorted Array in DSA C++ - 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.

int countOccurrences(const vector<int>& arr, int target) {
    int first = lower_bound(arr.begin(), arr.end(), target) - arr.begin();
    int last = upper_bound(arr.begin(), arr.end(), target) - arr.begin();
    return last - first;
}
    

This code finds how many times target appears in a sorted array using two binary searches.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two binary searches (lower_bound and upper_bound).
• How many times: Each binary search repeats steps about log n times, where n is array size.

How Execution Grows With Input

Each binary search cuts the search space in half repeatedly.

Input Size (n)	Approx. Operations
10	About 2 * 4 = 8 steps
100	About 2 * 7 = 14 steps
1000	About 2 * 10 = 20 steps

Pattern observation: Operations grow slowly, increasing by about 1 step each time input size multiplies by 2.

Final Time Complexity

Time Complexity: O(log n)

This means the time to count occurrences grows slowly, even if the array gets much bigger.

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 target's start and end positions, avoiding checking all elements.

Interview Connect

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

Self-Check

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