Complexity is a hot-topic and catchy phrase. Everyone agrees "Complexity is bad" and "simplicity is good", but the terms continue to be muddled in mixed meaning and over-use. This page serves as a series of notes on the terms. I don't agree with all the theories here, I'm just penning them down. I plan to update it over time (updating the date in the process). Let's begin.
Rich Hickey gave the iconic talk Simple Made Easy which proposes a distinction between 'easy' and 'simple'. The talk also seeks to turn complexity into an objective measure.
Kolmogorov complexity also seeks to turn complexity into an objective measure. It measures the length of the shortest computer program that produces the object as output.
Another theory has complexity as branching in code. Every if statement or switch statements increases complexity. This understanding breaks down when it comes to polymorphism where adding additional sub-instances which conform to some protocol don't increase complexity all that much. (or do they?)
Complexity is the size of the code (Number of lines, number of methods, number of characters, etc.)
Complexity is the use of a nail gun where a thumb tack would do. Using infrastructure that requires high setup time, maintenance, or cognitive load.
Complexity is using novel or untraditional tools.
Product
Product requirements are often a source of complexity. Having multiple types of users. Or some customers with slightly different behavior.
Hiding complexity behind configuration files or neater abstractions won't avoid the increased product complexity. If user's can configure their account with N different toggles then you have 2^N different account states that could cause issues. These will show up in bug reports. Perhaps some of them can be easily ruled out, but determining which configuration options are relevant is part of what makes measuring complexity so difficult.
Humor
"Complexity is any code written by someone else. Elegance is any code written by yourself (recently)." This gets at the subjective use of the term. It ties into Rich Hickey's concern with inflating 'easy' and 'simple'.
Other Notes
Complexity is the number of configuration states your application can be in"
-- Jussi Pakkanen's “Let’s play a game of not adding options”
"People say that Haskell is not complex, and that it is just different. But I think that is a useless statement. When the thing you are dealing with is vastly different from what you are used to, it can appear complex no matter how simple it actually is."
-- Learning Haskell - Miscellaneous Enlightenments
Big systems are often complex, but not all complex systems are big. Signs of complexity in software include the number of direct dependencies and the depth of the dependency tree, the number of integrations, the hierarchy of users and ability to dele-gate, the number of edge cases the system must control for, the amount of input from untrusted sources, the amount of legal variety in that input, and so on, and so forth.
-- Kill it with Fire - Marianne Bellotti