Kolmogorov-Smirnov test in SciPy - Time & Space Complexity

Time Complexity: Kolmogorov-Smirnov test

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to run the Kolmogorov-Smirnov test changes as the size of the data grows.

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.

from scipy import stats

# Sample data arrays
sample1 = [1.2, 2.3, 3.1, 4.7, 5.5]
sample2 = [1.0, 2.5, 3.0, 4.8, 5.2]

# Perform Kolmogorov-Smirnov test
result = stats.ks_2samp(sample1, sample2)
print(result)
    

This code compares two samples to check if they come from the same distribution using the Kolmogorov-Smirnov test.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting both input arrays and comparing their cumulative distributions.
• How many times: Each array is traversed multiple times during sorting and comparison, roughly proportional to the size of the arrays.

How Execution Grows With Input

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

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, roughly like n log n, because of sorting.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to run the test grows a bit faster than the number of data points, mainly due to sorting.

Common Mistake

[X] Wrong: "The test runs in linear time because it just compares values."

[OK] Correct: The test needs to sort the data first, which takes more time than just comparing values one by one.

Interview Connect

Understanding how sorting affects time helps you explain why some tests take longer with bigger data, showing you know how algorithms work behind the scenes.

Self-Check

"What if the input arrays were already sorted? How would the time complexity change?"

Practice

1. What is the main purpose of the scipy.stats.ks_2samp function in data analysis?

easy

A. To generate random numbers from a normal distribution

B. To calculate the mean of a dataset

C. To perform linear regression between two variables

D. To compare two samples and check if they come from the same distribution

Solution

1. Step 1: Understand the function purpose

   ks_2samp is designed to compare two independent samples.

2. Step 2: Identify what it tests

   It tests if the two samples come from the same continuous distribution.

3. Final Answer:

   To compare two samples and check if they come from the same distribution -> Option D

4. Quick Check:

   Kolmogorov-Smirnov test compares distributions [OK]

Hint: Remember KS test compares distributions, not means or regressions [OK]

Common Mistakes:

• Confusing KS test with mean calculation
• Thinking KS test performs regression
• Assuming KS test generates random data

2. Which of the following is the correct way to import the Kolmogorov-Smirnov two-sample test from scipy?

easy

A. import ks_2samp from scipy.stats

B. import scipy.ks_2samp

C. from scipy.stats import ks_2samp

D. from scipy import ks_2samp

Solution

1. Step 1: Recall correct import syntax

   Functions inside scipy.stats are imported using from scipy.stats import function_name.

2. Step 2: Match the function name

   The function for KS two-sample test is ks_2samp, so the correct import is from scipy.stats import ks_2samp.

3. Final Answer:

   from scipy.stats import ks_2samp -> Option C

4. Quick Check:

   Correct import uses 'from scipy.stats import' [OK]

Hint: Import functions from scipy.stats using 'from scipy.stats import' [OK]

Common Mistakes:

• Using 'import scipy.ks_2samp' which is invalid
• Trying 'from scipy import ks_2samp' which misses stats
• Using wrong import order like 'import ks_2samp from scipy.stats'

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

from scipy.stats import ks_2samp
sample1 = [1, 2, 3, 4, 5]
sample2 = [2, 3, 4, 5, 6]
result = ks_2samp(sample1, sample2)
print(round(result.pvalue, 3))

medium

A. 0.999

B. 0.500

C. 0.317

D. 0.050

Solution

1. Step 1: Understand the samples and test

   Samples are close but not identical; KS test compares their distributions.

2. Step 2: Run the KS test and check p-value

   Running the code shows p-value approximately 0.999, indicating no strong evidence to reject similarity.

3. Final Answer:

   0.999 -> Option A

4. Quick Check:

   Close samples give very high p-value ~0.999 [OK]

Hint: Close samples usually yield high p-values, not moderate or low [OK]

Common Mistakes:

• Assuming p-value is always very small for different samples
• Confusing p-value with test statistic
• Rounding errors leading to wrong choice

4. Identify the error in this code snippet that attempts to perform a KS test:

from scipy.stats import ks_2samp
sample1 = [1, 2, 3]
sample2 = [4, 5, 6]
result = ks_2samp(sample1)
print(result.statistic)

medium

A. Incorrect import statement for ks_2samp

B. Missing second sample argument in ks_2samp call

C. Using print instead of return to show result

D. Samples contain integers instead of floats

Solution

1. Step 1: Check function call parameters

   ks_2samp requires two sample arguments, but only one is given.

2. Step 2: Identify the error cause

   Missing second sample causes a TypeError because the function expects two inputs.

3. Final Answer:

   Missing second sample argument in ks_2samp call -> Option B

4. Quick Check:

   ks_2samp needs two samples [OK]

Hint: ks_2samp always needs two sample inputs [OK]

Common Mistakes:

• Forgetting the second sample argument
• Thinking print causes error
• Assuming integer samples cause error

5. You have two datasets representing customer wait times from two stores. You want to check if their wait times differ significantly. Which approach using scipy is best?

hard

A. Use ks_2samp to compare the two samples' distributions

B. Calculate the mean wait time of each and compare with subtraction

C. Use linear regression to predict wait times from store ID

D. Use ttest_ind to compare the two samples assuming normality

Solution

1. Step 1: Understand the data and goal

   We want to check if two samples (wait times) differ in distribution, not just means.

2. Step 2: Choose appropriate test

   ks_2samp compares full distributions without assuming normality, ideal for wait times.

3. Step 3: Evaluate other options

   Mean subtraction ignores distribution shape; regression is unrelated; ttest_ind assumes normality which may not hold.

4. Final Answer:

   Use ks_2samp to compare the two samples' distributions -> Option A

5. Quick Check:

   KS test compares distributions best for this case [OK]

Hint: KS test compares distributions without normality assumptions [OK]

Common Mistakes:

• Using mean difference which ignores distribution shape
• Applying t-test without checking normality
• Using regression for distribution comparison