Time functions of non-deterministic Turing machines (a better question) This is a more precise version of that question. 
Let $M$ be a non-deterministic Turing machine which recognizes a language $L$, that is, for every input word $u$ there is an accepting computation with input $u$ if and only if $u\in L$. 
Update Let us assume, as Joel suggested below that $M$ terminates on every  input. The simplest thing to assume is that if $u\in L$, the TM  eventually gives "yes" and if $u\not\in L$, it gives "no". 
The smallest time (number of steps)  of such a computation is denoted by $T_M(u)$. For every $n\ge 1$ we define $T_M(n)$ the maximum of all $T_M(u)$ for all accepted $u$ of length $\le n$. Then $T_M(n)\colon \mathbb{N}\to \mathbb{N}$ is the time function of $M$. If $M$ is a deterministic Turing machine, then its time function $T(n)$ is constructible that is there is a deterministic Turing machine which computes values $T(n)$ in time $\sim T(n)$. 
Question Let $T(n)$ be the time function of a non-deterministic TM. Is it constructible? Is it {\it polynomally time constructible} that is there is a deterministic TM computing $T(n)$ in time $\sim T(n)^d$ for some $d\ge 1$?
I expect the answer to be "no" in both cases. Is it known?
 A: The way you have set up the question, the answer is negative, even for deterministic machines. 
To see this, let $L$ be the halting problem, consisting of strings $u$ describing a Turing machine, which halts when started on an empty tape.
This language is recognized by a Turing machine $M$, which on input $u$ simply simulates the computation of that program on an empty tape, and accepts $u$ if this simulation halts. In other words, $u$ is in the language if and only if $u$ is accepted by some computation of $M$, which is what you requested. 
For $u$ that are accepted, the time complexity $T_M(u)$ is at least as large as the length of the computation of $u$ on the empty tape, since the simulation takes at least as long as the real thing. Thus, $T_M(n)$ is at least as large as the busy beaver function, since the number of states of the machine coded by a string $u$ is at most the length of $u$. This function is therefore not computable at all, let alone constructible. 
As I mentioned in my comment, however, one can avoid this kind of example if you insist that $M$ halts on all input, so that time complexity of $T_M(u)$ is defined not just for acceptable $u$ but also for unacceptable $u$. In this case, you can definitely compute $T_M(u)$ just by running it on all the input, and use this to take the max. But that wouldn't be constructible, which is why I thought maybe this is what you might actually have been interested in. But your reply to my comment says otherwise...
A: Your question is (almost?) equivalent to asking whether for a given $n$, there is $u$ of length $n$ for which the non-deterministic $M$ takes time $\ge t$. This is a decision question, where the (main) input $n$ is in unary. Unary languages (denoted $TALLY$) cannot be $NP$-complete, and what you're looking for seems to be a deterministic time bound for $TALLY\cap NP$, or rather, for $TALLY \cap NTIME(n^k)$. I would recommend asking this on cstheory.SE
