My awesome idea

Building on what I learned before about computational complexity (see previous blog post) I'm now making a great new device that could infer computational complexity! It'll be an Eclipse plugin; just press Ctrl+Shift+F7 while selecting a method and a message box pops up, showing, in big-O notation, how long it takes to run. To implement this, I'll need to use a lot of Java's metaprogramming techniques, but once I have that out of the way, it'll be simple. And it'll work for everything.

April fools!

Actually, this is fundamentally impossible to make. Why? The answer goes back to Alan Turing and the halting problem. The question of the halting problem is, is it possible to construct a program that can tell if another program will halt? Well, consider this program (in Wikipedia-style pseudocode):

function example()
    if halts?(example) then
        infinite-loop()
    else
        return nil

So, what happens when we run halts?(example)? Well, if this returns true, then example itself should go into an infinite loop, not halting. If it returns false, indicating that the example loops forever, then it in fact quickly returns nil and halts. So there's no real answer to whether this halts. And--it's not hard to see--there are (countably) infinitely many similar programs that exploit the same loophole.

When I first learned this, I thought, "This is cheating; that's too easy." Well, yes. That's higher level math for you. But there's another way of thinking about it, without that cheating device: to be able to tell if absolutely any piece of code halts, you need to know everything about that code and basically run it in some sort of emulator. There are cases where you can know it doesn't halt, but if it doesn't halt unexpectedly, and you're running the code... that doesn't work.

Building off of this, think about complexity: the first thing you need to know before assessing complexity is whether an algorithm halts. But we just showed that we can't do that! Also, what if the code does something like this:

function example2(n)
    if complexity(example2) = O(n) then
        return new integer[n][n]     // this takes O(n^2)
    else if complexity(example2) = O(n^2) then
        return new integer[n]        // this takes O(n)

and we want a tight bound for complexity.

Of course, specific solutions are possible, but these are both difficult to construct and highly limited in function. I hope you had fun with your daily dose of pessimism!