Comparing experiment runs in MLOps - Time & Space Complexity

Time Complexity: Comparing experiment runs

O(n²)

Understanding Time Complexity

When comparing experiment runs, we want to know how the time needed grows as we add more runs to compare.

We ask: How does the comparison time change when the number of runs increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

# Assume runs is a list of experiment results
for i in range(len(runs)):
    for j in range(i + 1, len(runs)):
        compare(runs[i], runs[j])

This code compares each experiment run with every other run exactly once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The nested loops that call compare on pairs of runs.
• How many times: For each run, it compares with all later runs, so roughly n*(n-1)/2 times.

How Execution Grows With Input

As the number of runs grows, the number of comparisons grows much faster.

Input Size (n)	Approx. Operations
10	45 comparisons
100	4,950 comparisons
1000	499,500 comparisons

Pattern observation: When input doubles, operations roughly quadruple, showing a fast growth.

Final Time Complexity

Time Complexity: O(n²)

This means the time to compare runs grows roughly with the square of the number of runs.

Common Mistake

[X] Wrong: "Comparing runs grows linearly because we just loop through the list once."

[OK] Correct: Each run is compared with many others, so the total comparisons grow much faster than just one loop.

Interview Connect

Understanding how nested comparisons grow helps you explain performance in real projects where many experiments need analysis.

Self-Check

"What if we only compared each run with a fixed number of recent runs? How would the time complexity change?"