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?"

Practice

1. What does the function np.percentile() calculate in a dataset?

easy

A. The value below which a given percentage of data falls

B. The average value of the dataset

C. The total sum of all data points

D. The number of data points in the dataset

Solution

1. Step 1: Understand percentile meaning

   A percentile indicates the value below which a certain percentage of data lies.

2. Step 2: Connect to np.percentile()

   The function np.percentile() returns this value for the given percentage.

3. Final Answer:

   The value below which a given percentage of data falls -> Option A

4. Quick Check:

   Percentile = value below % data [OK]

Hint: Percentile = cutoff value for given percent [OK]

Common Mistakes:

• Confusing percentile with mean or sum
• Thinking percentile counts data points
• Mixing percentile with total dataset size

2. Which of the following is the correct syntax to find the 25th percentile of a numpy array data?

easy

A. np.percentile(25, data)

B. np.percentile(data, 25)

C. np.percentile(data, percentile=25)

D. np.percentile(25%)

Solution

1. Step 1: Recall np.percentile() parameters

   The first argument is the data array, the second is the percentile number.

2. Step 2: Check each option

   np.percentile(data, 25) correctly uses np.percentile(data, 25). Others have wrong argument order or syntax.

3. Final Answer:

   np.percentile(data, 25) -> Option B

4. Quick Check:

   np.percentile(array, percentile) [OK]

Hint: First argument data, second percentile number [OK]

Common Mistakes:

• Swapping arguments order
• Using keyword 'percentile' incorrectly
• Adding % sign inside function

3. Given the array arr = np.array([10, 20, 30, 40, 50]), what is the output of np.percentile(arr, 40)?

medium

A. 20.0

B. 30.0

C. 26.0

D. 40.0

Solution

1. Step 1: Understand percentile calculation

   40th percentile means value below which 40% of data lies. Data sorted: [10,20,30,40,50]

2. Step 2: Calculate 40th percentile

   Position = (40/100)*(5-1) = 1.6. Interpolate between arr[1]=20 and arr[2]=30: 20 + 0.6*(30-20) = 26.0

3. Final Answer:

   26.0 -> Option C

4. Quick Check:

   40th percentile = 26.0 [OK]

Hint: Percentile index = p/100*(n-1), interpolate if needed [OK]

Common Mistakes:

• Picking nearest data point without interpolation
• Using wrong index calculation
• Confusing percentile with quartile

4. What is wrong with this code snippet to find the 90th percentile of data?

np.percentile(data, percentile=90)

medium

A. The data array must be sorted before calling np.percentile()

B. The percentile value must be between 0 and 1, not 90

C. The function should be called as data.percentile(90)

D. The keyword argument 'percentile' is invalid; percentile should be positional

Solution

1. Step 1: Check np.percentile() argument rules

   The function expects the percentile as the second positional argument, not as a keyword 'percentile'.

2. Step 2: Validate other options

   Percentile can be 90 (not 0.9), function is not a method of array, and sorting is handled internally.

3. Final Answer:

   The keyword argument 'percentile' is invalid; percentile should be positional -> Option D

4. Quick Check:

   Percentile argument is positional [OK]

Hint: Percentile must be second positional argument [OK]

Common Mistakes:

• Using invalid keyword argument
• Assuming percentile is fraction (0-1)
• Trying to sort data manually

5. You have a dataset data = np.array([5, 7, 8, 12, 15, 18, 22, 27, 30]). You want to find the value below which 75% of the data falls and then filter the dataset to only include values below this percentile. Which code correctly does this?

hard

A. threshold = np.percentile(data, 75)
filtered = data[data <= threshold]

B. threshold = np.percentile(data, 0.75)
filtered = data[data <= threshold]

C. threshold = np.percentile(data, 75)
filtered = data[data < threshold]

D. threshold = np.percentile(data, 75)
filtered = data[data > threshold]

Solution

1. Step 1: Calculate 75th percentile threshold

   Use np.percentile(data, 75) to get the value below which 75% data lies.

2. Step 2: Filter data including values equal to threshold

   Use <= to include values equal to threshold, so filtered = data[data <= threshold].

3. Final Answer:

   threshold = np.percentile(data, 75) filtered = data[data <= threshold] -> Option A

4. Quick Check:

   Percentile 75 + filter <= threshold [OK]

Hint: Use percentile value and filter with <= threshold [OK]

Common Mistakes:

• Using 0.75 instead of 75 for percentile
• Filtering with < instead of <=
• Filtering with > instead of <= or <