Regression testing in Software Engineering - Time & Space Complexity

Time Complexity: Regression testing

O(n) full, O(n + k) selective

Understanding Time Complexity

When studying regression testing, it is important to understand how the time to run a test suite grows as the codebase and number of tests increase.

We want to know how test execution scales and why test selection strategies matter.

Scenario Under Consideration

Analyze the time complexity of running a full regression test suite versus a selective suite.

Full regression:
    for each test_case in all_tests:
        setup test environment
        execute test
        compare actual vs expected result
        record pass/fail

Selective regression:
    affected_modules = analyze_dependencies(changed_files)
    for each test_case in all_tests:
        if test_case.module in affected_modules:
            execute test

Full regression runs every test. Selective regression uses dependency analysis to run only relevant tests.

Identify Repeating Operations

Look at what repeats in each approach.

• Full regression: Every test case is executed regardless of the change. The loop runs n times for n total tests.
• Selective regression: Dependency analysis runs once, then only tests mapped to affected modules execute — typically a fraction of n.

How Execution Grows With Input

As the project grows, the test suite grows with it.

Total Tests (n)	Full Regression	Selective (20% affected)
100 tests	100 executed	~20 executed
1,000 tests	1,000 executed	~200 executed
10,000 tests	10,000 executed	~2,000 executed

Pattern observation: Full regression is O(n) — every test runs. Selective regression is also O(n) for the filtering step but executes only O(k) tests where k is the number of affected tests, typically k << n.

Final Time Complexity

Full Regression: O(n) where n is the total number of test cases

Selective Regression: O(n + k) — O(n) to filter, O(k) to execute, where k is tests for affected modules

In practice, selective regression saves significant time because k is much smaller than n for localized changes.

Common Mistake

[X] Wrong: "We only need to test the code we changed, not anything else."

[OK] Correct: Changes in one module can break dependent modules. Regression testing must cover not just the changed code but all code that depends on it. This is why dependency analysis in selective regression includes affected modules, not just changed files.

Interview Connect

Understanding regression testing complexity helps explain CI/CD pipeline design decisions. Knowing when to use full vs selective regression is a common interview topic in QA and DevOps discussions.

Self-Check

If a project has 10,000 tests and average test execution takes 2 seconds, how long does a full regression run take? How would test parallelization across 10 machines change this?

Practice

1. What is the main purpose of regression testing in software development?

easy

A. To check that new code changes do not break existing features

B. To test the software performance under heavy load

C. To find security vulnerabilities in the software

D. To design the user interface of the application

Solution

1. Step 1: Understand regression testing goal

   Regression testing is done to ensure that recent code changes do not negatively affect existing functionality.

2. Step 2: Match purpose with options

   To check that new code changes do not break existing features clearly states this purpose, while others focus on performance, security, or design, which are different testing types.

3. Final Answer:

   To check that new code changes do not break existing features -> Option A

4. Quick Check:

   Regression testing = check existing features still work [OK]

Hint: Regression testing = verify old features after changes [OK]

Common Mistakes:

• Confusing regression testing with performance testing
• Thinking regression testing finds new bugs only
• Mixing regression testing with security testing

2. Which of the following is the correct way to describe an automated regression test?

easy

A. A script that runs tests automatically after code changes

B. A report summarizing user feedback

C. A manual checklist to verify UI changes

D. A design document for new features

Solution

1. Step 1: Identify automation in regression testing

   Automated regression tests are scripts that run automatically to check software after changes.

2. Step 2: Compare options to automation definition

   A script that runs tests automatically after code changes matches this exactly. Others describe manual or unrelated activities.

3. Final Answer:

   A script that runs tests automatically after code changes -> Option A

4. Quick Check:

   Automated regression test = automatic script [OK]

Hint: Automation means tests run by script, not manually [OK]

Common Mistakes:

• Confusing manual checks with automated tests
• Thinking reports or documents are tests
• Ignoring the 'automatic' part of regression testing

3. Consider this Python code snippet for a regression test automation check:

def test_model_accuracy(model, test_data, expected_accuracy):
    accuracy = model.evaluate(test_data)
    return accuracy >= expected_accuracy

class DummyModel:
    def evaluate(self, data):
        return 0.85

model = DummyModel()
result = test_model_accuracy(model, None, 0.80)
print(result)

What will be the output when this code runs?

medium

A. Error: 'NoneType' object is not iterable

B. False

C. True

D. 0.85

Solution

1. Step 1: Understand the evaluate method output

   The DummyModel's evaluate method returns 0.85 regardless of input.

2. Step 2: Check the comparison in test_model_accuracy

   It compares 0.85 >= 0.80, which is True, so the function returns True.

3. Final Answer:

   True -> Option C

4. Quick Check:

   0.85 >= 0.80 = True [OK]

Hint: Check returned value and compare to expected threshold [OK]

Common Mistakes:

• Assuming None input causes error
• Confusing returned accuracy with boolean result
• Ignoring the fixed return value of evaluate

4. You have this regression test code snippet in Python:

def run_regression_tests(tests):
    for test in tests:
        if not test():
            print("Test failed")
            break
    else:
        print("All tests passed")

def test1():
    return True

def test2():
    return False

run_regression_tests([test1, test2])

What is the output of this code?

medium

A. All tests passed

B. Test failed

C. No output

D. Error: break outside loop

Solution

1. Step 1: Analyze the loop over tests

   The loop runs test1() which returns True, so continues to test2().

2. Step 2: Check test2() result and loop behavior

   test2() returns False, triggering print("Test failed") and break to exit loop.

3. Final Answer:

   Test failed -> Option B

4. Quick Check:

   Second test fails, loop breaks, prints 'Test failed' [OK]

Hint: Loop breaks on first failed test, prints failure [OK]

Common Mistakes:

• Thinking else after for runs always
• Ignoring break statement effect
• Assuming all tests run regardless of failure

5. You want to improve your regression testing for a machine learning model that predicts house prices. Which approach best ensures your tests catch errors after model updates?

hard

A. Skip testing if training loss decreases

B. Manually check a few random predictions after each update

C. Only test the model when users report errors

D. Run automated tests comparing model predictions on a fixed test set before and after updates

Solution

1. Step 1: Identify best regression testing practice for ML models

   Automated tests on a fixed test set ensure consistent checks after updates.

2. Step 2: Evaluate options for reliability

   Run automated tests comparing model predictions on a fixed test set before and after updates uses automation and fixed data, catching errors reliably. Others rely on manual or reactive methods, which are less reliable.

3. Final Answer:

   Run automated tests comparing model predictions on a fixed test set before and after updates -> Option D

4. Quick Check:

   Automated fixed tests catch errors best [OK]

Hint: Use automated tests on fixed data to catch changes [OK]

Common Mistakes:

• Relying on manual checks only
• Ignoring testing until errors reported
• Assuming lower training loss means no bugs