How Complex is my Code?

Table of Contents

What is Complexity?

“Complexity of an algorithm is the amount of resources required to run it.”

(Wikipedia Definition)

Given this definition, there are so many definitions of Resources one can think of in terms of running code: the memory needed, the time needed, the mental resources to understand the code, the mental resources required to understand the problem, the context knowledge to understand how the code is solving it — all are reasonable interpretations of resources required to run code.

Computational Complexity

I had multiple lectures in university that pointed towards the question of “how complex is this code?”. Starting with formal definitions of a problem, how programs can be modelled to understand their resources, to the actual computation of how resource usage (time or memory) grows as input size grows. Looking at these topics as a software developer and no longer a computer science student, I only sometimes discover glimpses of those questions at work.

For example, the computational time complexity of this code would be O(n²)

, with n

the length of the list. In the worst case of a reverse-sorted list, this would perform, for each of the n elements of the list, n comparisons to the other list elements and then n swaps.

def insertion_sort(array: list[int]) -> list[int]:
for index in range(1, len(array)):
current = array[index]
predecessor = index - 1
while predecessor >= 0 and array[predecessor] > current:
array[predecessor + 1] = array[predecessor]
predecessor -= 1
array[predecessor + 1] = current
return array

A different implementation solving the same problem can vary in computational complexity. Sorting by creating a map of all possible values in the list up front, for example, would be faster with O(n)

. This implementation would first need O(n)

for finding the max, then O(n)

for looping through the values and placing them in the count array, and again O(k)

for the construction of the result, where k

is the highest value.

def counting_sort(array: list[int]) -> list[int]:
count = [0] * (max(array) + 1)
for current in array:
count[current] += 1
result = []
for current, frequency in enumerate(count):
result.extend([current] * frequency)
return result

Analysing the number of operations that an algorithm might perform gave a hint that the second algorithm could be more performant. But in this case, it raises the question: at what cost? The first function was easy to understand, as it mirrors how many people intuitively sort — just start at one and place each next element in its spot in the sorted part of the array. The second is harder to understand: it creates a list that depends on the maximum value, which might be unnecessarily large for a list like [4500, 9000, 7200]

, and it is constrained because negative numbers cannot be sorted.

For a software developer, simply choosing an algorithm with a lower computational complexity might introduce a different form of complexity, costing not computing-time resources, but more time to understand the function, time to document and communicate its limitations, and time to fix issues if somebody used it with the wrong sets of numbers.

Domain Code Complexity

I define my job as writing business / domain code. For me, computing time and computer memory are cheap resources compared to human thinking time and human memory. 50 initialised variables are a problem, not because the virtual AWS machines I run my code on struggle, but because the developer who needs to spend hours every time they read the function to understand the reason behind the 50 variables.

Therefore, I ask, how can I measure how complex my code is for a human?

Sure, lines of code is a simplification of complexity — everyone knows that many lines can be frustrating, but even two lines can hide enough complexity to keep one occupied for hours.

Cyclomatic Complexity

Cyclomatic Complexity counts the number of linearly independent paths through code — that is, the number of if

, for

, while

, and case

branches (plus 1 for the method declaration).

There is solid research showing a correlation between high Cyclomatic Complexity and defect density. A heatmap over the repository can also identify why modules have high complexity, which can be great for refactoring prioritisation. A function with high complexity is most likely doing more than it should, and might benefit from delegating some of its responsibility. It also gives a nice basis for estimating how many tests are needed to cover a function, in relation to its number of execution paths.

The Cyclomatic Complexity of both insertion_sort

and counting_sort

is 3 - both have two loops + 1. For this example, both implementations appear to have the same complexity. It doesn’t capture semantic complexity, background knowledge, or unintuitive limitations.

Halstead Complexity

Halstead Complexity follows the idea that mental effort scales with the number of distinct concepts you need to hold in working memory. Halstead argued that to understand a program, you need to learn each distinct operator, and on average you need to see an operator twice to learn it (once to encounter it, once to confirm it). A program is harder to understand the more distinct operands (array

, current

, …) it has that are rarely reused, and the more distinct operators (for

, +

, =

, …) it has.

HALSTEAD_LEARNING_CONSTANT = 2
# The variety of operators and operands that make a function complex
halstead_difficulty = (distinct_operator_count / HALSTEAD_LEARNING_CONSTANT) * (total_operands / distinct_operand_count)
# The bits needed to encode the function
halstead_volume = (total_operators + total_operands) * log_2(distinct_operator_count + distinct_operand_count)
# Estimated mental effort
halstead_cognitive_complexity = halstead_difficulty * halstead_volume

This gives the result that counting_sort

is less difficult and, although it has a higher volume, is cognitively less complex.

# insertion_sort
halstead_difficulty = (12 / 2) * (24 / 6) = 6 * 4 = 24
halstead_volume = 46 × log₂(18) = 46 × 4.17 = 192
# counting_sort
halstead_difficulty = (13 / 2) × (27 / 10) = 6.5 × 2.7 = 17.6
halstead_volume = 51 × log₂(23) = 51 × 4.52 = 230

While this is a very cool measurement of mental complexity, Halstead measures token reuse density, not conceptual difficulty. The longer I think about this question, the more I think the answer lies not in computer science, but in linguistics.

Linguistic Complexity

Psycholinguistics studies how humans process language and has identified some reliable predictors of reading difficulty:

Familiarityknown words are processed faster than unknown ones. The equivalent in code is whether a pattern (like sorting an array in an intuitive way) is immediately recognised or requires decoding. Skill level also matters here, as programming patterns or even new concepts likematch

statements can be unfamiliar to individuals.Working memory loadsentences (and functions) with many nested clauses are harder because you have to hold unresolved structure in mind.Coherencetext is easier when each sentence connects clearly to the previous one. In code, this can relate to the distance between a variable declaration and its usage, but also to whether the goal of a function reads as a clear thought or a mess of statements.

Linguistic Complexity Measurements

Even a superficial look into linguistic complexity compared to programming complexity reveals shared properties. Historically, both seem to have influenced each other. Natural language inspiring formal languages and formal grammar did form the basis for compilers, and vice versa, programming complexities like Cyclomatic Complexity inspired parse trees in linguistics; to just name one of many examples.

Subordination index Count of subordinate clauses, each of which adds