# What is the complexity of timing a turing machine? [duplicate]

I can't find the standard name for this problem, so lets call it TIMING, it takes as input a Turing machine $F$ with its input $i$, and a number of steps $n$. It returns yes if $F(i)$ halts in less than $n$ steps, otherwise it returns no. What is the time complexity of this problem in terms of $n$, is it $n\log n$ as it is similar to a universal Turing machine, or does the counting each step mean it takes longer.

• This is the bounded halting problem. – Raphael Oct 18 '16 at 14:50