Percentiles and quantiles in SciPy - Time & Space Complexity

Time Complexity: Percentiles and quantiles

O(n log n)

Understanding Time Complexity

We want to know how the time to calculate percentiles or quantiles 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_90 = np.percentile(data, 90)
quantile_25 = np.quantile(data, 0.25)

This code generates 1000 random numbers and finds the 90th percentile and 25th quantile.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the array to find the percentile or quantile.
• How many times: The sorting happens once per percentile or quantile calculation.

How Execution Grows With Input

Sorting takes more time as the list gets longer, 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 operations grow a bit faster than the input size, but not as fast as squaring it.

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 because of sorting.

Common Mistake

[X] Wrong: "Finding a percentile is just picking one number, so it should be very fast regardless of data size."

[OK] Correct: To find the correct percentile, the data usually needs to be sorted first, 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 an approximate method that does not sort the entire data? How would the time complexity change?

Practice

1. What does the 90th percentile represent in a dataset?

easy

A. The average of the top 90% of data

B. The value below which 90% of the data falls

C. The value above which 90% of the data falls

D. The middle value of the dataset

Solution

1. Step 1: Understand percentile definition

   A percentile indicates the value below which a given percentage of observations fall.

2. Step 2: Apply to 90th percentile

   The 90th percentile means 90% of data points are below this value.

3. Final Answer:

   The value below which 90% of the data falls -> Option B

4. Quick Check:

   Percentile = value below % data [OK]

Hint: Percentile = value below that percent of data [OK]

Common Mistakes:

• Confusing percentile with average
• Thinking percentile is value above percentage
• Mixing percentile with median

2. Which of the following is the correct way to find the 25th percentile using scipy.stats?

easy

A. stats.quantile(data, 25)

B. stats.percentile(data, 0.25)

C. stats.mquantiles(data, prob=0.25)

D. stats.scoreatpercentile(data, 25)

Solution

1. Step 1: Recall scipy function for percentile

   The function to find percentile is stats.scoreatpercentile with arguments (data, percentile).

2. Step 2: Check options

   stats.scoreatpercentile(data, 25) uses stats.scoreatpercentile(data, 25), which is correct for 25th percentile.

3. Final Answer:

   stats.scoreatpercentile(data, 25) -> Option D

4. Quick Check:

   Use scoreatpercentile for percentiles [OK]

Hint: Use stats.scoreatpercentile(data, percentile) [OK]

Common Mistakes:

• Using wrong function names like percentile or quantile
• Passing 0.25 instead of 25 for percentile
• Confusing quantiles with percentiles

3. Given the data array [10, 20, 30, 40, 50], what is the output of stats.scoreatpercentile(data, 40)?

medium

A. 26.0

B. 22.0

C. 30.0

D. 20.0

Solution

1. Step 1: Understand percentile calculation

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

2. Step 2: Calculate 40th percentile using interpolation

   Position = (40/100)*(n-1) = 0.4*4 = 1.6. Interpolate between data[1]=20 and data[2]=30: 20 + 0.6*(30-20) = 20 + 6 = 26.0.

3. Final Answer:

   26.0 -> Option A

4. Quick Check:

   Interpolation gives 26.0 [OK]

Hint: Percentile position = p/100*(n-1), interpolate values [OK]

Common Mistakes:

• Choosing nearest data point without interpolation
• Using index p instead of p/100*(n-1)
• Confusing percentile with median

4. The code below is intended to find the quartiles of data using scipy but raises an error. What is the error?

import scipy.stats as stats
data = [5, 10, 15, 20, 25]
quartiles = stats.mstats.mquantiles(data, prob=[0.25, 0.5, 0.75])
print(quartiles)

medium

A. mquantiles requires numpy array, not list

B. prob argument should be a single float, not a list

C. No error, code runs correctly

D. mquantiles is not in scipy.stats.mstats

Solution

1. Step 1: Check function location and usage

   stats.mstats.mquantiles is a valid function and accepts prob as a list for multiple quantiles.

2. Step 2: Check input data type

   mquantiles accepts list or array-like data, so list input is valid.

3. Final Answer:

   No error, code runs correctly -> Option C

4. Quick Check:

   mquantiles accepts list and prob list [OK]

Hint: mquantiles accepts list and prob list [OK]

Common Mistakes:

• Assuming mquantiles only accepts numpy arrays
• Thinking prob must be a single float
• Confusing function location in scipy

5. You have a dataset of exam scores: [55, 70, 65, 80, 90, 85, 75]. You want to divide the scores into four equal groups (quartiles) using scipy. Which code snippet correctly computes the quartiles?

hard

A. stats.mstats.mquantiles(scores, prob=[0.25, 0.5, 0.75])

B. stats.scoreatpercentile(scores, [25, 50, 75])

C. np.percentile(scores, [0.25, 0.5, 0.75])

D. stats.mstats.mquantiles(scores, prob=[25, 50, 75])

Solution

1. Step 1: Identify correct function for quartiles

   Quartiles are quantiles at 25%, 50%, and 75%. stats.mstats.mquantiles accepts prob as fractions between 0 and 1.

2. Step 2: Check options for correct prob format

   stats.mstats.mquantiles(scores, prob=[0.25, 0.5, 0.75]) uses prob=[0.25, 0.5, 0.75], which is correct. stats.scoreatpercentile(scores, [25, 50, 75]) uses scoreatpercentile but with a list, which is invalid. np.percentile(scores, [0.25, 0.5, 0.75]) uses numpy but with fractions instead of percentages. stats.mstats.mquantiles(scores, prob=[25, 50, 75]) uses prob with values >1, which is invalid.

3. Final Answer:

   stats.mstats.mquantiles(scores, prob=[0.25, 0.5, 0.75]) -> Option A

4. Quick Check:

   mquantiles prob values are fractions [OK]

Hint: Use mquantiles with prob as fractions (0.25, 0.5, 0.75) [OK]

Common Mistakes:

• Passing percent values instead of fractions to prob
• Using scoreatpercentile with list of percentiles
• Confusing numpy percentile input format