To what extent can an algorithm predict the time complexity an arbitrary input program? The Halting problem states that it is impossible to write a program that can determine if another program halts, for all possible input programs. 

I can, however, certainly write a program that can compute the running time of a program of  like:

for(i=0; i&lt;N; i++)
    { x = 1; }


and return a time complexity of $N$, without ever running it. 

For all other input programs, it would return a flag indicating it was unable to determine the time-complexity.

My question is this:

What conditions must hold, such that we can algorithmically determine the time-complexity of a given program?

*If there is a canonical reference or review article to this I would appreciate a link to it in the comments.
In general you cannot determine complexity, even for halting programs: let $T$ be some arbitrary Turing machine and let $p_T$ be the program (that always returns 0):

input: n
run T for n steps
if T is in halting state, output: 0
otherwise, loop for n^2 steps and output: 0


It is clear that it is undecidable in general whether $p_T$ is linear-time or quadratic-time. 

However, much work has been carried out on the effective computation of program complexity. I have particular fondness for Implicit Complexity Theory which aims at creating languages that, using special constructs or type disciplines, allows one to write only programs that inhabit a certain well-defined complexity class. By what I consider to be something of a miracle, these languages are often complete for that class!

One particularly nice example is described in this paper by J.-Y. Marion, which describes a tiny imperative language, with a type discipline inspired from information-flow and security analysis techniques, which allows a characterization of algorithms in P.