np.argsort() for sort indices in NumPy - Time & Space Complexity

Time Complexity: np.argsort() for sort indices

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to find sorted indices changes as the input array grows.

Specifically, how does np.argsort() behave when sorting larger arrays?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

arr = np.random.rand(1000)
sorted_indices = np.argsort(arr)

This code creates an array of 1000 random numbers and finds the indices that would sort the array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The sorting algorithm compares and rearranges elements to find the order.
• How many times: The sorting process involves multiple comparisons and swaps, repeating many times depending on array size.

How Execution Grows With Input

As the array size grows, the number of operations grows faster than just a simple increase.

Input Size (n)	Approx. Operations
10	About 30 to 40 operations
100	About 600 to 700 operations
1000	About 10,000 to 12,000 operations

Pattern observation: The operations grow faster than the input size itself, roughly multiplying by a bit more than n each time.

Final Time Complexity

Time Complexity: O(n log n)

This means the time needed grows a bit faster than the size of the array, but not as fast as checking every pair individually.

Common Mistake

[X] Wrong: "Sorting indices with np.argsort() takes time proportional to the array size only (O(n))."

[OK] Correct: Sorting requires comparing elements multiple times, so it takes more time than just looking at each element once.

Interview Connect

Knowing how sorting scales helps you explain performance when working with data. It shows you understand how algorithms behave with bigger inputs.

Self-Check

"What if we used np.argpartition() instead of np.argsort()? How would the time complexity change?"