Software Design/Document function's algorithmic complexity

Checklist items:

• Algorithmic complexity is documented for a function (command, remote API endpoint)?
• Important performance implications (disk I/O, database queries, etc.) are documented for a function?

Why

Specifying function's algorithmic complexity allows users to reason about their uses of the function and avoid creating too complex algorithms (such as when the function has complexity O(N) and is called from an inner loop in some code). Users may decide to cache the result(s) of an expensive function. On the other hand, caching would be deemed unnecessary if the function was cheap (had O(1) complexity).

Apart from algorithmic complexity, there are other types of performance implications of a function call which may better be documented:

• Disk IO: reading or writing.
• Database queries (and their complexity).
• RPC calls.

It's especially important to document the non-trivial complexity of functions that developers usually expect to be cheap, such as size() of a collection.

Complexity and performance implications may need to be documented for classes that implement a command, or an action to be executed, as well as for remote API endpoints (such as REST API).

Why not

• Complexity shouldn't be documented for operations that are not be expected to be executed in performance-demanding contexts.
• In general, performance may not be an important property of the software being developed.
• When the complexity of operation matches the expectations of users: for example, the complexity of functions whose names start with get- being O(1), or the complexity of a function like sum(collection) being O(N), documenting the complexity may be superfluous.

These points make, in fact, documenting algorithmic complexity and performance implications of a function a rarely applicable practice in most projects.

Documenting the algorithmic complexity of an operation and the information such as that an operation performs database queries means exposing the implementation details in the API which is an antipattern itself because it imposes compatibility constraints which might make the code harder to change in the future. This might be especially limiting when low complexity is documented, that is, that a function is cheap.

Related Practices

• Don't use get- prefix in the name of an expensive function