Computing complexity

Is there a way to automatically compute the complexity of a piece of code?

Comment viewing options


You could have stated a simpler question.

There's always the master lemma, I guess. Yes, you can derive a lot of complexities automatically, but I haven't seen it yet. But, in general, no. It cannot be done, since you cannot even prove halting trivially.

[ Duh, guess that was an assignment? Darn ;) ]

It depends

It depends on whether you mean 'arbitrary' code, whether you're willing to accept a semi-decision, how much precision you need, and the extent to which the language and runtime has non-local properties that affect complexity (such as lazy computes, multimethods, reflection, lazy IO, GC costs, aspect oriented or constraint satisfaction elements, parallelization, virtual memory, CPU cache, optimizations, etc.).

If you need precision and decidability for the complexity computation, then you'll need to greatly restrict the expressivity of the language to something both less than Turing complete and designed to support this analysis.

[If this was a homework assignment, shame on you.]

Nope, just

Nope, just curiosity...

Luckily it's been a couple years since I was last subject to homework :)

It's like SAT -- hard, but

It's like SAT -- hard, but we're doing it anyways. Off the top of my head, see projects by Jacob Burnim, Sumit Gulwani, and Simon Goldsmith from the past few years for some different but surprisingly effective approaches.

Linear Logical Algorithms, a

Linear Logical Algorithms, a previous discussion here on LtU.

If you can express your piece of code in linear logic, you can infer its' complexity.