# How come this turing machine running time is $O(n^{1+\log_2 2006}\cdot \log_2n)$

Given a deterministic Turing machine with an input tape and a work tape. The work tape is restricted to $\log_2 n+100$ cells ($n$ represents the input length) and its tape alphabet is of size $2006$. Moreover, the Turing machine has $27$ states.

I wonder how come the running time of such machine is $O(n^{1+\log_2 2006}\cdot \log_2n)$ (The answer is the correct choice for this multiple choices question out of an exam I practise)

• I dont get this question. What is Aleph Bet signs? Please formulate proper sentences. – A.Schulz Dec 14 '12 at 19:20

So let us quickly get a bound for the number of configurations. You have $100+\log n$ possible positions for the head on the work tape and $n$ positions for the head on the input tape. The work tape can contain $2006^{100+\log n}$ different words. Furthermore there are 27 states. Combining everything gives \begin{align} 27n \cdot (100+\log n) \cdot 2006^{100+\log n}&=27\cdot2006^{100}(100n+n\log n) n^{\log 2006}\\ &=O((100n+ n\log n) n^{\log 2006})\\ &=O(\log n\cdot n^{1+\log 2006})\\ \end{align}