# 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. Commented Dec 14, 2012 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}
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 1, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://cs.stackexchange.com/questions/7398/how-come-this-turing-machine-running-time-is-on1-log-2-2006-cdot-log-2n", "fetch_time": 1718967927000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2024-26/segments/1718198862070.5/warc/CC-MAIN-20240621093735-20240621123735-00635.warc.gz", "warc_record_offset": 158283033, "warc_record_length": 39203, "token_count": 339, "char_count": 1140, "score": 3.5, "int_score": 4, "crawl": "CC-MAIN-2024-26", "snapshot_type": "latest", "language": "en", "language_score": 0.7820552587509155, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00037-of-00064.parquet"}