How should I document a method's computational complexity in the code?

Question

I am currently working on a project that has very little documentation overall. The team is working to change that. I am doing my part, by adding xml comments to the methods I make and the ones I edit, so that the automatic documentation generation tools can use them.

For some methods, complexity is either obvious or irrelevant.

But for some other methods, the way the code is built right now, they can seem like they are pretty light, but actually be very slow (talking about n³ and above here).

Of course, I am aware that there is an underlying problem and that refactoring is probably needed. But we neither have the time nor the budget to refactor everything within a reasonable delay, so in the meanwhile, I would like to communicate this information as a warning.

example:

/// <summary>
/// Tests if a thing is in a valid state. WARNING: This runs in O(n³)
/// </summary>
/// <returns>The validity of the thing</returns>
public virtual bool IsSomethingValid()
{
    return DoCodeThatIsMoreComplexThanItLooks();
}

I usually find those cases when doing some performance improvements, but at this point, this happens pretty often, and I think adding such big warnings too often will lose its impact.

So my idea would be to simply add it to the standard XML comment format, and put the complexity regardless of what it is, as a bit of information that may be useful or interesting.

Is there a standard way to communicate the complexity of a method in XML comments? like a tag that Visual Studio will understand (but doesn't add by default).

Answer 1

If the complexity is relevant for users of the method, then the best approach is to state it in the summary field as in your example. Of course it should clearly state what n represent, since it is not clear from the method signature.

C# has two kinds of comments, XML comments and regular comments. XML comments are used to generate documentation and are shown in tooltip help, code completion etc. So XML comments is documentation for the users of the the method. Regular comments inside code is for documentation of the implementation which is not relevant outside the method.

The question is when is complexity information relevant for a user? Only in the cases where the user would have the choice between using different algorithms with different trade-offs. But then you also need to state the other aspects of the trade-off (e.g large constant overhead), otherwise the user would just always select the one with the lowest complexity and there would be no purpose to having other options.

If the user does not really have a choice, then the complexity is pretty irrelevant. If you want to document it it should be in a regular comment inside the method.

For example what is the purpose of the warning in a validation method? Can the user just decide to skip the validation? Probably not.