Update #6:
Wow, quick service on TCS StackExchange! Emanuele Viola has provided an answer Are runtime bounds in P decidable? Answer: No.
Emanuele's answer illuminates (for me) Luca Trevisan's answer Do runtimes for P require exp resources to upper-bound? Answer: yes.
Thus, I am becoming pretty optimistic of being able to post, pretty soon, a reasonably reliable (partial) summary of the computational complexity of runtime estimation for algorithms in P (it's harder than one might guess).
In the meantime, please see Emanuele's and Luca's answers.
Update #5:
I am pleased to report steady progress toward a summary answer -- a key remaining question, that has just been asked on TCS StackExchange, is Are runtime bounds in P decidable?
My thanks go to all who have helped/are helping this particular researcher.
Update #4:
As I work through the many fine comments—and Luca Trevisan's construction in particular—a summary narrative is slowly crystallizing, that eventually I will post here (once I gain sufficient confidence in it). For now, there is a preliminary draft posted on the Gödel's Lost Letter weblog ... where comments are welcome.
At present I grasp many of the tricks of complexity theory pretty well, but the motivating ideas beind these tricks often are opaque (to me), for reasons that Mac Lane describes:
Analysis is full of ingenious changes of coordinates, clever substitutions, and astute manipulations. In some of these cases, one can find a conceptual background. When so, the ideas so revealed help us understand what's what. We submit that this aim of understanding is a vital aspect of mathematics.It is the "understanding of what's what" that as yet has not crystallized (for me) ... and yet I am very appreciative and grateful for the help that has been given so generously, to me and to many on this fine forum.
Update #3:
On MathOverflow, Luca Trevisan has posted an interesting new comment relating to runtime estimation that (as I parse his comment) raises issues that are broadly associated to the practical feasibility of generating concrete runtime estimates.
I apologize for my slowness in producing a summary trace-back of these issues ... realistically it may take quite awhile to produce a summary of these questions-and-answers that respects the existing literature, and has lasting value, not only to TCS students, but to the broader community of mathematicians, scientists and engineers who care about these issues.
Update #2:
I have rated as "accepted" Luca Trevisan's ingenious construction, which answers the question as reframed by Tsuyoshi Ito. Hopefully I have grasped correctly that, in brief, Luca's construction yields the answers "yes" and "yes for all practical purposes" (FAPP).
It will take awhile (for me anyway) to appreciate whether Luca's $M$-machines obstruct the $P$-time uniform reduction of ${BQP}^{P}\,\to\,{BQP}$ that is at the heart of the original question posed on MathOverflow, that question being, "Does BQP^P = BQP? ... and what proof machinery is available?"
In turn, this was a generalization of a question that was posed by Dick Lipton and Ken Regan on their weblog Gödel's Lost Letter and P=NP, the question "Is Factoring Really In BQP? Really?"
After some further reflection (which may take a few days) I will attempt a summary back-trace of this chain of questions, which so enjoyably unites elements of mathematics, science and practical engineering.
In the meantime, my thanks and appreciation are extended to everyone ... and further comments are very welcome, of course!
Update #1:
I greatly admire Tsuyoshi Ito's comment, which (because it appears below the break) I will quote here in full:
I think that you are asking the following. For a Turing machine M and an integer n≥0, let f(M,n) be the maximum number of steps required for M to halt on the input x over the strings x∈{0,1}^n. The question I believe you are asking here is whether there exists a polynomial-time Turing machine M such that computing f(M,n) requires time exponential in n. (Note that M is not part of the input.)
I therefore ask that answers be addressed to Tsuyoshi's formulation (rather than my original clumsier formulation). Keep in mind that $M\in P$ is given, so that for each $M$ we have $f(M,n)\le n^{k(M)}$ for some (unknown $M$-dependent) $k(M)$. Moreover, please don't forget also that if your answer is "yes", then please either specify a concrete instance of M, or else, state your view as to whether M is constructible. And if your answer is "no", then please describe (if possible) an algorithm for computing f(M,n) that requires only n-polynomial time. And please have fun too! :)
Do runtimes for algorithms in P require EXP resources to upper-bound? ... are concrete examples known?
After some thought, I posted this question on MathOverflow, rather than here on TCS Theory in consequence of a (possibly wrong) intuition that the answers would be "yes" and "yes" ... for details, see the MathOverflow question.
In the event that the answer is known to TCS cognoscenti to be "no"—such that a runtime bounding algorithm (itself in P) that encompasses all algorithms in P can be concretely given—then that answer too would be very interesting and valuable.
Please consider contributing an answer to this cross-disciplinary question on MathOverflow ... or if you prefer to post your answer(s) here in TCS Theory, then eventually I will summarize them on MathOverFlow too.
Also, please accept my thanks and appreciation for this wonderful site.