Don't ruin the complexity of your interface with checking.
diff --git a/CppCoreGuidelines.md b/CppCoreGuidelines.md
index 7ccb8a2c7..ef03b1102 100644
--- a/CppCoreGuidelines.md
+++ b/CppCoreGuidelines.md
@@ -749,7 +749,7 @@ The date is validated twice (by the `Date` constructor) and passed as a characte
 ##### Example
 
 Excess checking can be costly.
-There are cases where checking early is dumb because you may not ever need the value, or may only need part of the value that is more easily checked than the whole.
+There are cases where checking early is dumb because you may not ever need the value, or may only need part of the value that is more easily checked than the whole.  Similarly, don't add validity checks that change the asymptotic behavior of your interface (e.g., don't add a `O(n)` check to an interface with an average complexity of `O(1)`).
 
     class Jet {    // Physics says: e*e < x*x + y*y + z*z
 

I'm not sure if this is redundant with the existing text "or may only need part of the value that is more easily checked than the whole."  (A more aggressive change would excise that clause.)
