Lambda the Ultimate

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 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.]

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 previous discussion here on LtU.

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