ANOVA (f_oneway) in SciPy - Time & Space Complexity

Time Complexity: ANOVA (f_oneway)

O(n)

Understanding Time Complexity

We want to understand how the time needed to run ANOVA using scipy's f_oneway grows as we add more data.

Specifically, how does the number of groups and their sizes affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from scipy.stats import f_oneway

# Example groups with data
group1 = [1, 2, 3, 4]
group2 = [2, 3, 4, 5]
group3 = [3, 4, 5, 6]

# Perform ANOVA test
f_stat, p_val = f_oneway(group1, group2, group3)
    

This code runs an ANOVA test to compare the means of three groups of numbers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Calculating group means and variances by scanning each data point.
• How many times: Each data point in all groups is visited once to compute sums and sums of squares.

How Execution Grows With Input

As the total number of data points across all groups grows, the work grows roughly the same amount.

Input Size (total data points)	Approx. Operations
10	About 10 visits to data points
100	About 100 visits to data points
1000	About 1000 visits to data points

Pattern observation: The time grows linearly with the total number of data points.

Final Time Complexity

Time Complexity: O(n)

This means the time to run ANOVA grows directly in proportion to the total number of data points.

Common Mistake

[X] Wrong: "Adding more groups makes the time grow exponentially."

[OK] Correct: The time grows with total data points, not the number of groups alone. More groups with few points each still means less work than fewer groups with many points.

Interview Connect

Understanding how ANOVA scales helps you explain performance when working with larger datasets in real projects.

Self-Check

"What if we used more groups but kept the total data points the same? How would the time complexity change?"