Percentiles with np.percentile() in NumPy - Time & Space Complexity

Time Complexity: Percentiles with np.percentile()

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to find percentiles changes as the data size grows.

How does the work increase when we have more numbers to analyze?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

data = np.random.rand(1000)
percentile_25 = np.percentile(data, 25)
percentile_50 = np.percentile(data, 50)
percentile_75 = np.percentile(data, 75)

This code finds the 25th, 50th, and 75th percentiles of a list of 1000 random numbers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the array to find the percentile positions.
• How many times: Sorting happens once per percentile call, but sorting dominates the cost.

How Execution Grows With Input

As the number of data points grows, sorting takes more time, but not in a simple doubling way.

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

Pattern observation: The work grows faster than the input size but slower than its square, roughly like n times log n.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to find percentiles grows a bit faster than the number of data points, mainly because of sorting.

Common Mistake

[X] Wrong: "Finding a percentile is just picking a value, so it takes the same time no matter the data size."

[OK] Correct: To find the percentile, the data usually needs to be sorted or partially sorted, which takes more time as data grows.

Interview Connect

Understanding how sorting affects percentile calculations helps you explain performance in data analysis tasks clearly and confidently.

Self-Check

"What if we used a method that finds percentiles without full sorting? How would the time complexity change?"