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)
This bound comes from the number of possible configurations. If you do more steps than you have configurations, you are in a cycle.
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}$$
