Can Big-O Complexity Be Detected at Compile Time?

When we learn algorithm analysis, we usually practice by looking at a piece of code and asking questions such as: how many times does this loop run? Is there another loop inside it? Does this search scan an entire collection? Does this recursion split the problem in half?

After a while, we start recognizing these patterns almost automatically.

A for loop iterating over a collection tends to suggest O(n). Two nested loops may indicate O(n²). Binary search points us toward O(log n). An efficient sorting algorithm usually lands around O(n log n).

That raises an interesting question:

If we can recognize these patterns by reading code, could the compiler do the same?

That is exactly the question that led me to explore building a Roslyn analyzer capable of estimating algorithmic complexity at compile time.

The short answer is: yes, to a certain extent.

The more interesting answer is understanding where that “to a certain extent” begins.

---

Big-O does not measure how long a method takes

Before talking about compilers, it is worth clarifying something important.

Big-O does not measure time in milliseconds.

When we say an algorithm is O(n²), we are not saying it is necessarily slow. We are describing how its computational cost grows as the input size increases.

Consider:

for (var i = 0; i < items.Count; i++)
{
    Process(items[i]);
}

If we assume Process has constant cost, we have approximately:

T(n) = n

Therefore:

O(n)

Now add another loop:

foreach (var item in items)
{
    foreach (var other in items)
    {
        Compare(item, other);
    }
}

In this case:

T(n) = n × n

which gives us:

O(n²)

Big-O ignores constants and less relevant details so we can focus mainly on the rate of growth.

That is why it remains useful even across completely different machines.

MIT, for example, introduces asymptotic complexity and recurrences early in its algorithms curriculum precisely because they provide a language for reasoning about growth without depending on specific hardware.

But that abstraction also creates the first challenge for automated analysis: to infer Big-O, we need to understand not only the syntax of the code, but also the meaning of the operations being executed.

---

The compiler knows much more about our code than it seems

This is where Roslyn makes the idea interesting.

The C# compiler does not see a source file as plain text.

It builds a structured representation of the program called a Syntax Tree. The syntax tree represents declarations, expressions, loops, method calls, conditionals, and practically every other language construct.

That means an analyzer does not need to search for strings such as:

"foreach"

It can ask directly:

Is there a ForEachStatementSyntax here?

More importantly, Roslyn also provides a Semantic Model.

That difference is significant.

Imagine:

items.Contains(value);

Looking only at the text, we do not know very much.

Contains could belong to:

List<T>
HashSet<T>
Dictionary<TKey, TValue>
IEnumerable<T>
MyCustomCollection

And those operations may have very different costs.

The Semantic Model can resolve the actual symbol referenced by the expression and reveal types, methods, arguments, and relationships between program elements. Roslyn's own documentation explains that the syntax tree alone is not enough to determine what an identifier actually refers to; that responsibility belongs to the semantic layer.

It is precisely this combination of syntax and semantics that makes much more sophisticated analysis possible.

---

A seemingly innocent example

Consider this code:

foreach (var item in items)
{
    if (otherItems.Contains(item))
    {
        Process(item);
    }
}

If otherItems is a List<T>, Contains may scan the list looking for the element.

If items has n elements and otherItems has m, we can model the cost approximately as:

O(n × m)

If both collections grow at roughly the same rate:

O(n²)

Now change the data structure:

HashSet<int> otherItems;

The exact same line of code:

otherItems.Contains(item);

has a very different expected algorithmic behavior.

The text barely changed.

The semantics changed significantly.

A complexity analyzer therefore needs to resolve the symbol and recognize known operations from the libraries being used.

In ComplexityAnalysis.Analyzers, this is one of the strategies I use: known BCL and LINQ operations are identified by the symbol resolved by Roslyn, not simply by the method name. This prevents a custom method named Contains from automatically being treated as if it were List<T>.Contains.

That detail may seem small, but it is exactly the kind of distinction that separates an interesting demo from a usable analysis tool.

---

Loops are the easy part

Finding loops is relatively straightforward.

The challenge begins when we need to understand what happens inside them.

Consider:

foreach (var item in items)
{
    Calculate(item);
}

What is the complexity?

We do not know.

If:

Calculate(item);

is O(1), then we have:

O(n)

But if Calculate scans another collection of size m, we may have:

O(n × m)

Or perhaps:

O(n²)

depending on the relationship between the inputs.

That is why a more sophisticated analyzer needs to move beyond purely local analysis.

---

Interprocedural analysis

This is where interprocedural analysis comes in.

Imagine:

void Process(IEnumerable<int> items)
{
    foreach (var item in items)
    {
        Search(item);
    }
}

And:

void Search(int item)
{
    foreach (var value in values)
    {
        if (value == item)
            return;
    }
}

Analyzing only Process is not enough.

We need to follow the call to Search.

We can think of it like this:

Process
    |
    +-- loop n
            |
            +-- Search
                    |
                    +-- loop m

Therefore:

O(n × m)

This kind of analysis can reveal some interesting relationships.

For example:

A → B O(n)

results in:

A O(n)

While:

loop n → B O(n)

results approximately in:

O(n²)

ComplexityAnalysis.Analyzers performs this kind of analysis within defined limits, following reachable methods and substituting called-method parameters with caller inputs when that can be done safely.

But there is a very important word here:

limits.

An analyzer that runs during compilation cannot explore the application's entire call graph indefinitely.

---

The analyzer also needs to be fast

There is an interesting irony in all of this.

It would be strange to build a performance analyzer that made compilation extremely slow.

Roslyn analyzers can run while we are writing code and during the build. That means analysis cost matters. Roslyn itself supports concurrent execution of analyzer actions to improve performance, provided the analyzer has been designed to operate safely in parallel.

A practical tool therefore needs to enforce analysis budgets.

For example:

maximum call depth = 5
methods analyzed per root = 32

If the analysis exceeds that budget, it needs to stop.

That decision matters because there is a difference between:

building a theoretically impressive analyzer

and:

building an analyzer that developers are willing to keep enabled in Visual Studio.

---

And then we get to recursion

Recursion makes things even more interesting.

Consider:

int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}

We can represent its cost with a recurrence:

T(n) = T(n - 1) + O(1)

which gives us:

O(n)

Now consider divide and conquer:

T(n) = 2T(n/2) + n

Applying the Master Theorem:

O(n log n)

Another example:

T(n) = 3T(n/2) + n

results approximately in:

O(n^1.585)

So an analyzer can go beyond simply counting loops. It can recognize certain recursive patterns, construct a recurrence, and attempt to solve it.

In the project I have been developing, support is intentionally limited to known families: simple reduction, some exponential recurrences, forms compatible with the Master Theorem, and a restricted subset of Akra-Bazzi.

The important word, once again, is restricted.

Because trying to solve every possible recurrence quickly takes us into very different territory.

---

So why can't we infer everything?

This is where we reach the theoretical limit.

It is tempting to imagine an analyzer that could receive any program and correctly answer:

This method is O(1).
This one is O(log n).
This one is O(n).
This one is O(n²).

For any arbitrary piece of code.

That is not possible in general.

Static program analysis runs into fundamental limits related to computability. The halting problem shows that there is no algorithm capable of correctly deciding, for every program and input, whether that program will terminate.

More general results, such as Rice's theorem, show that non-trivial semantic properties of programs are undecidable in general. Cornell's program analysis material summarizes the practical consequence particularly well: static analyses need to work with approximations.

That completely changes the question.

Instead of asking:

“How can we determine the complexity of any program?”

we should ask:

“For which structures can we produce a sufficiently safe conclusion?”

That is a much more productive question.

---

Sometimes “I don't know” is the best answer

This may be the principle I like most about this kind of tool.

Consider:

foreach (var item in items)
{
    ExecuteSomething(item);
}

If ExecuteSomething lives in an external library the analyzer knows nothing about, there are several options.

It could simply assume:

O(1)

But that could be completely wrong.

It could assume:

O(n)

But that would also be arbitrary.

A much safer alternative is to return:

Unknown

In other words:

“I don't have enough information to state the complexity.”

That may sound less impressive, but it is an important characteristic of serious analysis tools.

Constant false positives destroy trust.

After a while, developers start ignoring the analyzer.

That is why I would rather have a tool miss some cases than invent certainty.

There is an interesting parallel with static analysis in general: when a property cannot be determined precisely, we need to define how we want to approximate it. Compiler and program analysis courses deal directly with this trade-off between precision, decidability, and conservatism.

---

Big-O does not replace other metrics either

Another important point: algorithmic complexity is not the same thing as code quality.

A method can be:

O(1)

and still be almost impossible to understand.

It may contain dozens of conditionals, multiple levels of nesting, too many responsibilities, and an enormous signature.

That is why it makes sense to look at different metrics independently.

Cyclomatic complexity attempts to represent independent control-flow paths.

Cognitive Complexity attempts to approximate the effort required to understand a given flow. SonarSource created this metric specifically to address aspects of understandability that are not well represented by cyclomatic complexity alone.

We can also track:

nesting depth
NLOC
statement count
parameter count
token count

None of these metrics replaces the others.

They answer different questions.

Big-O essentially asks:

“How does cost grow with the input?”

Cognitive Complexity asks something closer to:

“How difficult is this flow to follow mentally?”

Combining those two ideas into a single score would probably create more confusion than insight.

---

Where this becomes genuinely useful

The goal of detecting complexity at compile time should not be to attach an academic label to every method.

The real value appears when we can detect dangerous changes in algorithmic behavior.

Imagine someone writes:

foreach (var customer in customers)
{
    if (blockedCustomers.Contains(customer.Id))
    {
        ...
    }
}

During development, the dataset is small and everything runs quickly.

In production:

customers = 100,000
blockedCustomers = 80,000

Now that data structure choice starts to matter.

If blockedCustomers is a list, the algorithm may perform an enormous number of comparisons.

Choosing a more appropriate data structure can completely change the expected behavior.

The analyzer does not need to prove the system's exact performance.

It needs to be able to say:

“There is a linear operation inside an iteration that depends on input size. You may want to take a closer look.”

That kind of feedback is valuable precisely because it happens before production, before benchmarking, and potentially even before code review.

---

Static analysis does not eliminate benchmarks

It is also important not to make a promise the tool cannot keep.

An O(n) method may be slower than an O(n²) method for small inputs.

Allocation, cache locality, I/O, branch prediction, concurrency, GC, databases, networks, JIT compilation, and many other factors influence real-world performance.

Big-O is about asymptotic growth.

Benchmarking is about concrete behavior under specific conditions.

Tracing and profiling show what actually happened during execution.

These tools complement each other.

I like to think about it this way:

Static analysis
    ↓
Where might there be a problem?

Benchmark
    ↓
What is the actual cost?

Profiling / tracing
    ↓
Where is execution time actually being spent?

Using one does not eliminate the need for the others.

---

The compiler as an architectural feedback tool

Exploring Big-O through Roslyn led me to a broader conclusion.

Compilers do not have to exist only to transform source code into assemblies.

Roslyn turns the compiler into a platform on top of which we can build tools that understand program syntax, symbols, and semantics. Microsoft itself presents this as one of the platform's core goals.

That lets us move many checks closer to the moment when a decision is made.

Instead of discovering certain problems in Sonar after a push, in code review a few hours later, or in production weeks later, we can provide feedback while the developer is still writing the method.

That idea is particularly interesting from an architecture perspective.

Whenever an architectural rule can be expressed objectively, there is a possibility of turning it into:

analyzer
architecture test
CI rule
source generator
linter
policy

It is a shift from passive documentation to executable feedback.

Not every architectural decision can or should become an automated rule.

But some certainly can.

---

What I learned while exploring this idea

The original question seemed simple:

“Can Big-O be detected at compile time?”

After exploring the problem, I think a better formulation is:

“Which complexity properties can we infer safely enough to provide useful feedback to developers?”

The difference matters.

We are not trying to build an oracle.

We are building a conservative analysis of a known subset of the language.

Loops, known operations, LINQ, certain interprocedural calls, and some families of recurrences can produce very useful results.

Dynamic code, difficult-to-resolve dispatch, unknown libraries, complex data dependencies, and structures outside the known model may remain Unknown.

And that is fine.

In tools like this, knowing when not to make a claim is part of the quality of the analysis.

---

Key takeaways

Big-O can be partially inferred at compile time because Roslyn provides much more than text: we have syntax trees, symbols, types, and semantic information.

The problem becomes interesting when we move beyond counting loops and start understanding operations, method calls, and recurrences.

There is no algorithm, however, that can perfectly determine semantic properties like these for every arbitrary program. Practical tools need to work with known subsets and conservative approximations.

An Unknown result can be far better than a fabricated estimate.

And perhaps most importantly, Big-O analysis does not replace benchmarks, profiling, cyclomatic complexity, or Cognitive Complexity. Each technique answers a different question.

The real gain is being able to move certain performance and design signals much closer to the moment when code is being written.

---

Where to go next

For anyone who wants to explore the topic in more depth, I would recommend a few directions.

• Microsoft Learn — .NET Compiler Platform SDK / Roslyn APIs: start with the Syntax Tree, Semantic Model, Symbols, and Diagnostic Analyzer APIs. The official documentation even includes a complete tutorial for building an analyzer and a code fix.
• MIT OpenCourseWare — Introduction to Algorithms: excellent material for strengthening your understanding of asymptotic analysis, recurrences, divide and conquer, and algorithm fundamentals.
• Introduction to Algorithms — Cormen, Leiserson, Rivest, and Stein (CLRS): still one of the best references for algorithms, asymptotic analysis, and recurrences.
• Compilers: Principles, Techniques, and Tools — Aho, Lam, Sethi, and Ullman: useful for understanding compilers, intermediate representations, program analysis, and optimization.
• Cornell Program Analysis materials: particularly useful for understanding data-flow analysis, conservative approximations, undecidability, and the theoretical limits of static analysis.
• Cognitive Complexity by SonarSource: a useful read for understanding why algorithmic complexity, cyclomatic complexity, and understandability are related but distinct concerns.

If you want to look at a practical implementation of these ideas, ComplexityAnalysis.Analyzers applies this reasoning with Roslyn to Big-O analysis, interprocedural calls, selected forms of recursion, and complementary complexity metrics, always preferring Unknown when a safe conclusion cannot be reached.

In the end, perhaps the most interesting part of this exercise is not automatically determining whether a method is O(n) or O(n²).

It is realizing how much knowledge is available at compile time, and how many engineering decisions we can turn into useful feedback before code ever reaches production.