To what extent can an algorithm predict the time complexity an arbitrary input program?
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.