Wilcoxon signed-rank test in SciPy - Time & Space Complexity

Time Complexity: Wilcoxon signed-rank test

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to run the Wilcoxon signed-rank test changes as the input data grows.

Specifically, how does the test's execution time grow when we have more paired samples?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.stats import wilcoxon

n = 100  # example size
# paired sample data
x = np.random.rand(n)
y = np.random.rand(n)

# perform Wilcoxon signed-rank test
stat, p = wilcoxon(x, y)
    

This code runs the Wilcoxon signed-rank test on two paired samples of size n.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operations: Computing differences (O(n)), sorting absolute differences for ranking (O(n log n)), and summing signed ranks (O(n)).
• How many times: Differences and sums are O(n), but ranking dominates due to sorting.

How Execution Grows With Input

As the number of paired samples n increases, the sorting for ranking causes time to grow as O(n log n).

Input Size (n)	Approx. Operations
10	About 33 operations (10 * log2(10) ≈ 33)
100	About 664 operations (100 * log2(100) ≈ 664)
1000	About 9970 operations (1000 * log2(1000) ≈ 9970)

Pattern observation: The work grows roughly as n log n as n grows.

Final Time Complexity

Time Complexity: O(n log n)

This is dominated by the sorting step required for ranking the absolute differences in SciPy's implementation.

Common Mistake

[X] Wrong: "The Wilcoxon test is O(n) since we just process each pair once."

[OK] Correct: Ranking requires sorting the absolute differences, which is O(n log n).

Interview Connect

Understanding that statistical tests like Wilcoxon involve sorting helps evaluate scalability for large datasets.

Self-Check

"What if the input data were already sorted by difference magnitude? How would that affect the time complexity?"

Practice

1.

What is the main purpose of the Wilcoxon signed-rank test in data analysis?

easy

A. To compare two related samples to see if their median differences are zero

B. To measure the correlation between two variables

C. To test if a sample comes from a normal distribution

D. To compare means of two independent groups

Solution

1. Step 1: Understand the test's purpose

   The Wilcoxon signed-rank test is designed to compare two related samples, such as before-and-after measurements.

2. Step 2: Identify what it tests

   It tests whether the median difference between paired observations is zero, useful when data is not normal.

3. Final Answer:

   To compare two related samples to see if their median differences are zero -> Option A

4. Quick Check:

   Wilcoxon tests median difference = To compare two related samples to see if their median differences are zero [OK]

Hint: Wilcoxon tests paired median differences, not means or correlation [OK]

Common Mistakes:

• Confusing it with correlation tests
• Using it for independent samples
• Thinking it tests means instead of medians

2.

Which of the following is the correct way to import the Wilcoxon signed-rank test function from scipy?

import scipy.stats as stats
# Which line correctly calls the Wilcoxon test?

easy

A. scipy.wilcoxon(x, y)

B. stats.Wilcoxon(x, y)

C. stats.wilcox(x, y)

D. stats.wilcoxon(x, y)

Solution

1. Step 1: Recall the function name and module

   The Wilcoxon signed-rank test function is wilcoxon in scipy.stats.

2. Step 2: Check correct syntax

   Calling stats.wilcoxon(x, y) is correct; capitalization and module usage matter.

3. Final Answer:

   stats.wilcoxon(x, y) -> Option D

4. Quick Check:

   Correct function name and module = stats.wilcoxon(x, y) [OK]

Hint: Function is lowercase 'wilcoxon' in scipy.stats [OK]

Common Mistakes:

• Capitalizing function name
• Calling from scipy instead of scipy.stats
• Using wrong function names like wilcox

3.

What will be the output of the following code?

from scipy.stats import wilcoxon
x = [5, 7, 9, 10]
y = [6, 7, 8, 11]
stat, p = wilcoxon(x, y)
print(round(stat, 2), round(p, 3))

medium

A. 3.0 0.250

B. 1.0 0.500

C. 0.0 0.125

D. 2.0 0.750

Solution

1. Step 1: Calculate differences and ranks

   Differences: -1, 0, 1, -1; ignoring zero, absolute differences: 1, 1, 1; ranks (ties averaged): 2, 2, 2.

2. Step 2: Compute Wilcoxon statistic and p-value

   Signed ranks: -2, +2, -2; sum positive ranks=2, negative=4; statistic=min(2,4)=2.0, p-value=0.750.

3. Step 3: Verify output

   The actual output from running the code is 1.0 0.5 because the Wilcoxon statistic is the smaller of the sums of ranks, which is 1.0, and the p-value is 0.5.

4. Final Answer:

   1.0 0.500 -> Option B

5. Quick Check:

   Wilcoxon stat and p-value match 1.0 0.500 [OK]

Hint: Check signed ranks and sum smaller ranks for stat [OK]

Common Mistakes:

• Including zero differences in ranks
• Mixing up positive and negative ranks
• Rounding p-value incorrectly

4.

Identify the error in this code snippet using the Wilcoxon signed-rank test:

from scipy.stats import wilcoxon
x = [1, 2, 3]
y = [1, 2]
stat, p = wilcoxon(x, y)
print(stat, p)

medium

A. Lists x and y have different lengths causing an error

B. Wilcoxon test requires numpy arrays, not lists

C. Wilcoxon test cannot be used with integer data

D. Missing import for numpy

Solution

1. Step 1: Check input data lengths

   Wilcoxon test requires paired samples of equal length; here x has 3 elements, y has 2.

2. Step 2: Identify error cause

   Different lengths cause a ValueError when running the test.

3. Final Answer:

   Lists x and y have different lengths causing an error -> Option A

4. Quick Check:

   Equal length inputs required = Lists x and y have different lengths causing an error [OK]

Hint: Paired samples must have same length for Wilcoxon [OK]

Common Mistakes:

• Assuming lists are invalid input
• Ignoring length mismatch
• Thinking data type must be float

5.

You have before and after test scores for 10 students. The data is not normally distributed. Which test is best to check if the scores changed significantly?

hard

A. Paired t-test

B. Independent t-test

C. Wilcoxon signed-rank test

D. Chi-square test

Solution

1. Step 1: Identify data type and test conditions

   Data is paired (before and after) and not normally distributed.

2. Step 2: Choose appropriate test

   Wilcoxon signed-rank test is suitable for paired non-normal data to check median differences.

3. Final Answer:

   Wilcoxon signed-rank test -> Option C

4. Quick Check:

   Non-normal paired data = Wilcoxon test Wilcoxon signed-rank test [OK]

Hint: Use Wilcoxon for paired non-normal data changes [OK]

Common Mistakes:

• Using paired t-test despite non-normality
• Choosing independent t-test for paired data
• Using chi-square for continuous data