8 Testing, Debugging, and Algorithmic Efficiency

A practical guide to designing effective tests, debugging failures, reasoning about correctness, analyzing algorithmic efficiency, and maintaining reliable programs.

From requirements to effective tests

Reliable software development combines four related activities: testing reveals that behavior differs from requirements, investigates why the difference occurred, correctness reasoning checks whether the algorithm meets its specification for all permitted inputs, and efficiency analysis examines whether the solution remains practical as inputs grow.

A useful records:

The input data.
The preconditions that must already hold.
The expected result or behavior.
The observed result produced by the program.
Whether the result passes or fails.

Testing should be based on requirements rather than only on examples that happen to work. A test suite organizes multiple tests and uses assertions to compare actual behavior with expected behavior.

For a function that returns the largest value in a nonempty list, representative tests could include:

[4, 9, 2], expecting 9, for an ordinary case.
[-5, -2, -8], expecting -2, for all-negative input.
[7], expecting 7, for a one-element input.
[3, 3, 3], expecting 3, for repeated values.
[], expecting an explicit error or a defined special result, because the stated requirement is that the list be nonempty.

The empty-list example is important: undocumented behavior at an invalid or unsupported input is a common source of defects.

Takeaway: define expected behavior before judging whether an implementation is correct.

Normal, boundary, edge, and invalid inputs

A strong test suite samples different categories of input because testing every possible input is usually impractical.

Normal cases represent common valid use. testing examines values at and around a limit. If scores from 0 through 100 are valid, useful tests include
$-1$ , $0$ , $1$ , $99$ , $100$ , and $101$ . These tests can expose an incorrect comparison such as using a strict limit when an inclusive limit is required, or a loop that begins or ends at the wrong position.

An is unusual but still relevant to the requirements. Examples include:

An empty string, list, or file.
A one-element collection.
Duplicate values.
Very large or very small numbers.
Negative numbers or zero.
Already sorted or reverse-sorted data.
Missing, extra, or malformed input.
The first or last item in a sequence.
A condition that occurs exactly once or never occurs.

Invalid-input tests should check both detection and response. Depending on the specification, the expected response may be an error message, an error value, an exception, or a request for new input. The program should not silently return a misleading result.

Takeaway: choose tests that challenge limits, assumptions, and error handling, not just ordinary successful cases.

A systematic process

Testing tells you that a failure exists; investigates its cause. A repeatable process is more reliable than changing random lines until one test happens to pass.

Reproduce the failure with the smallest input that still demonstrates the problem.
Record the expected and actual behavior precisely.
Locate the failure using output, assertions, logs, a debugger, or a failing test.
Form a specific hypothesis about the responsible condition or assumption.
Check the hypothesis by inspecting relevant values and control flow.
Change one cause at a time.
Rerun the reproducing test.
Run the full test suite to detect unintended effects.
Keep a for the corrected defect.

For example, a positive-value counter that loops with range(1, len(values)) skips the item at index 0. Testing [4] reveals the problem immediately: the function returns 0 even though one value is positive. Inspecting the loop range identifies the cause. Iterating directly over each value removes the skipped-first-element defect and avoids unnecessary index manipulation.

Takeaway: isolate one failure, verify one hypothesis, make one focused change, and preserve the example that exposed the bug.

Reasoning about correctness

Correctness is stronger than passing a few examples. An algorithm is correct when it produces the required result for every input satisfying its stated conditions and terminates as required.

A states what must be true before execution begins. A states what must be true when execution finishes. A is a property preserved before and after each iteration.

Consider a linear search for a target in a list. Before each iteration, the items already examined do not contain the target. If the algorithm finds the target, returning true satisfies the result requirement. If the loop ends, every item has been examined and none equals the target, so returning false is justified.

When reviewing an algorithm, ask:

Does it handle every allowed category of input?
Are loop bounds correct?
Can a variable be used before it has a valid value?
Does every execution path produce an appropriate result?
Does the algorithm terminate?
Are error conditions handled explicitly?
Does the implementation match the specification and data representation?

Testing supplies evidence about selected inputs; invariants and related reasoning explain why the behavior extends to all permitted inputs.

Takeaway: state the contract, identify what remains true during execution, and connect the final state to the required result.

Efficiency, growth, and trade-offs

Efficiency concerns the resources an algorithm uses, especially running time and memory. Let the input size be $n$ . Two algorithms can produce the same correct result while having very different growth as $n$ increases.

notation summarizes asymptotic growth:

A single loop through a list is usually $O(n)$ time.
Two nested loops that each process all items are often $O(n^2)$ time.
Repeatedly halving a search space, as in binary search on sorted data, is $O(\log n)$ time.
A direct calculation independent of input size is $O(1)$ time.

For duplicate detection, comparing every pair can require $O(n^2)$ worst-case time. Recording previously seen values in a set usually reduces the running time to $O(n)$ , but uses $O(n)$ additional memory. This is a time-space trade-off: reducing one resource can require more of another.

A responsible improvement process is:

Build the simplest clearly correct solution.
Write tests that define its behavior.
Measure or analyze performance on representative input sizes.
Identify the actual bottleneck.
Select a better algorithm or data structure when justified.
Rerun correctness, edge-case, and regression tests.
Document the new time and space costs.

Do not sacrifice correctness for an unjustified speed improvement. A fast algorithm that produces incorrect results is not a successful solution.

Takeaway: analyze how time and memory grow, then optimize only after correctness and the actual bottleneck are understood.

Documentation and the complete workflow

Documentation makes intended behavior and constraints visible to other programmers and to your future self. Useful documentation states:

The problem being solved.
Valid input ranges and preconditions.
Parameter meanings and return values.
Expected errors or exceptions.
Important assumptions.
Time and space complexity.
Non-obvious design decisions.
Examples that clarify use.

Comments should explain why a non-obvious decision is necessary rather than merely repeating what the code does. Well-named tests also serve as executable documentation: a test name communicates required behavior, and an assertion records the expected result.

A complete workflow is:

Clarify inputs, outputs, constraints, and error behavior.
Choose a representation that fits the problem.
Design a simple algorithm or pseudocode.
State preconditions, postconditions, or invariants.
Implement in small, focused pieces.
Create normal, boundary, edge, and invalid-input tests.
Run tests and inspect failures.
Debug systematically.
Analyze time and space growth.
Improve only when justified and preserve regression tests.
Document assumptions, complexity, and limitations.

Takeaway: a maintainable solution makes its behavior, assumptions, complexity, and important decisions easy to verify.