Mann-Whitney U test in SciPy - Time & Space Complexity

Time Complexity: Mann-Whitney U test

O((n + m) log(n + m))

Understanding Time Complexity

We want to understand how the time needed to run the Mann-Whitney U test changes as the size of the input data grows.

Specifically, how does the test's execution time increase when we have more data points?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.stats import mannwhitneyu

data1 = np.random.rand(1000)
data2 = np.random.rand(1000)

stat, p = mannwhitneyu(data1, data2)
print(f"U statistic: {stat}, p-value: {p}")
    

This code runs the Mann-Whitney U test on two arrays of random numbers, each with 1000 elements, to compare their distributions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing and ranking all combined elements from both input arrays.
• How many times: The algorithm processes all elements together, so it handles about n + m elements, where n and m are the sizes of the two arrays.

How Execution Grows With Input

As the number of data points increases, the time to rank and compare grows faster than just adding more elements.

Input Size (n = m)	Approx. Operations
10	About 20 elements ranked and compared
100	About 200 elements ranked and compared
1000	About 2000 elements ranked and compared

Pattern observation: The work grows roughly proportional to the total number of elements times the log of that number, because sorting is involved.

Final Time Complexity

Time Complexity: O((n + m) log(n + m))

This means the time to run the test grows a bit faster than just the total number of data points, mainly because it sorts all the data combined.

Common Mistake

[X] Wrong: "The Mann-Whitney U test runs in linear time because it just compares elements once."

[OK] Correct: The test needs to sort or rank all combined data points, which takes more time than just one pass through the data.

Interview Connect

Understanding how sorting affects the time needed for statistical tests like Mann-Whitney U helps you explain your approach clearly and shows you know how data size impacts performance.

Self-Check

"What if one input array is much smaller than the other? How would that affect the time complexity?"

Practice

1. What is the main purpose of the Mann-Whitney U test in data analysis?

easy

A. To test if a single sample mean equals a known value

B. To compare two independent groups without assuming normal distribution

C. To measure the correlation between two variables

D. To analyze the variance among multiple groups

Solution

1. Step 1: Understand the test purpose

   The Mann-Whitney U test is a non-parametric test used to compare two independent groups.

2. Step 2: Identify the key feature

   It does not assume the data follows a normal distribution, unlike t-tests.

3. Final Answer:

   To compare two independent groups without assuming normal distribution -> Option B

4. Quick Check:

   Non-parametric comparison = C [OK]

Hint: Remember: Mann-Whitney compares two groups without normality [OK]

Common Mistakes:

• Confusing it with correlation tests
• Assuming it compares means only
• Using it for more than two groups

2. Which of the following is the correct way to import the Mann-Whitney U test function from scipy?

easy

A. import scipy.mannwhitneyu as mw

B. import mannwhitneyu from scipy.stats

C. from scipy import mann_whitney_u_test

D. from scipy.stats import mannwhitneyu

Solution

1. Step 1: Recall scipy.stats module functions

   The Mann-Whitney U test function is named mannwhitneyu and is inside scipy.stats.

2. Step 2: Check correct import syntax

   The correct Python import syntax is from scipy.stats import mannwhitneyu.

3. Final Answer:

   from scipy.stats import mannwhitneyu -> Option D

4. Quick Check:

   Correct import syntax = B [OK]

Hint: Use 'from scipy.stats import mannwhitneyu' to import [OK]

Common Mistakes:

• Using wrong module or function name
• Incorrect import syntax
• Trying to import with 'import ... as' incorrectly

3. What will be the output of the following code snippet?

from scipy.stats import mannwhitneyu
x = [1, 3, 5]
y = [2, 4, 6]
stat, p = mannwhitneyu(x, y)
print(round(stat, 2), round(p, 3))

medium

A. 3.0 0.5

B. 4.5 0.25

C. 6.0 0.05

D. 0.0 1.0

Solution

1. Step 1: Understand the data and test

   Lists x and y have values [1,3,5] and [2,4,6]. Mann-Whitney U test compares ranks between these two groups.

2. Step 2: Calculate Mann-Whitney U statistic and p-value

   Using scipy, the U statistic is 3.0 and p-value is 0.5 (two-sided test by default).

3. Final Answer:

   3.0 0.5 -> Option A

4. Quick Check:

   U=3.0, p=0.5 from scipy output [OK]

Hint: Run code to get exact U and p values quickly [OK]

Common Mistakes:

• Mixing up U statistic with p-value
• Rounding incorrectly
• Assuming p-value is always small

4. Identify the error in this Mann-Whitney U test code and select the fix:

from scipy.stats import mannwhitneyu
x = [1, 2, 3]
y = [4, 5, 6]
stat, p = mannwhitneyu(x, y, alternative='greater')
print(stat, p)

medium

A. Replace mannwhitneyu with mann_whitney_u

B. Change 'alternative' to 'two-sided'

C. No error; code runs correctly

D. Use 'alternative="greater"' with capital G

Solution

1. Step 1: Check function parameters

   The mannwhitneyu function accepts an alternative parameter with values 'two-sided', 'less', or 'greater'.

2. Step 2: Verify code correctness

   Using alternative='greater' is valid and the function call is correct.

3. Final Answer:

   No error; code runs correctly -> Option C

4. Quick Check:

   Correct parameter usage = D [OK]

Hint: Check scipy docs for valid 'alternative' values [OK]

Common Mistakes:

• Using wrong alternative string case
• Trying to use non-existent function names
• Assuming default alternative is 'greater'

5. You have two small samples with skewed data: a = [2, 3, 5, 7] and b = [1, 4, 6, 8]. You want to test if sample a tends to have higher values than b. Which scipy Mann-Whitney U test call is correct?

hard

A. mannwhitneyu(a, b, alternative='greater')

B. mannwhitneyu(a, b, alternative='less')

C. mannwhitneyu(a, b, alternative='two-sided')

D. mannwhitneyu(b, a, alternative='greater')

Solution

1. Step 1: Define the hypothesis direction

   We want to test if a tends to have higher values than b, so the alternative hypothesis is 'greater'.

2. Step 2: Choose correct function call

   The call should be mannwhitneyu(a, b, alternative='greater') to test if a is stochastically greater than b.

3. Final Answer:

   mannwhitneyu(a, b, alternative='greater') -> Option A

4. Quick Check:

   Test if a > b = A [OK]

Hint: Use 'alternative="greater"' when testing if first sample is larger [OK]

Common Mistakes:

• Swapping sample order and alternative incorrectly
• Using 'less' when testing for greater
• Choosing 'two-sided' when direction matters