On proving time constructibility of functions (Q1059393)

The paper contains two theorems about sufficient conditions for time constructibility of functions. The theorems are in fact a formalization of the essence of some proofs dealing with time constructibility known from the literature. Two cases are treated separately. The first theorem covers the case of functions for which the condition \[ (\exists \epsilon >0)[f(n)\geq (1+\epsilon)n,\quad for\quad almost\quad all\quad n] \] holds. The second theorem applies to functions f with f(n)\(\geq n\) but not meeting the above condition. Using the theorem, time constructibility of functions like \(\lfloor n^ p\rfloor (p\geq 1),n!,2^ n,2^{2^ n},...,n\lfloor \lfloor \log n\rfloor^ p\rfloor,...,n\lfloor (\log^*n)^ p\rfloor\), \(n_ 1\cdot n_ 2\), \(n+\lfloor n^ p\rfloor (0<p<1),n+\lfloor \lfloor \log n\rfloor^ p\rfloor,n+\lfloor (\log^*n)^ p\rfloor\), etc. can be proved on a few lines.