np.searchsorted() for insertion points in NumPy - Time & Space Complexity

Time Complexity: np.searchsorted() for insertion points

O(m log n)

Understanding Time Complexity

We want to understand how the time needed to find insertion points grows as the input size increases when using np.searchsorted().

How does the number of operations change when we search in bigger arrays?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

arr = np.sort(np.random.randint(0, 1000, size=1000))
values = np.array([10, 500, 999])
indices = np.searchsorted(arr, values)
print(indices)

This code finds the positions where each value in values should be inserted in the sorted array arr to keep it sorted.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each value, a binary search is done on the sorted array.
• How many times: Once per value in the values array.

How Execution Grows With Input

Each search takes time that grows slowly as the array size grows, and the total time grows linearly with the number of values searched.

Input Size (n)	Approx. Operations
10	About 30 operations (3 per search x 10 values)
100	About 700 operations (7 per search x 100 values)
1000	About 10,000 operations (10 per search x 1000 values)

Pattern observation: The search per value grows slowly with array size, but total work grows roughly with the number of values searched.

Final Time Complexity

Time Complexity: O(m log n)

This means the time grows linearly with the number of values searched (m) and logarithmically with the size of the sorted array (n).

Common Mistake

[X] Wrong: "The search time grows linearly with the size of the array for each value."

[OK] Correct: The search uses binary search, which splits the array repeatedly, so it grows much slower than linear, only logarithmically.

Interview Connect

Understanding how search operations scale helps you explain efficient data lookups and insertion points, a useful skill in many data science tasks.

Self-Check

"What if the array was not sorted? How would the time complexity of finding insertion points change?"