Assuming that f(n) >= n.

If possible, I'd like a proof in terms of Turing machines. I understand the reason why with machines that run on binary, because each "tape cell" is a bit with either 0 or 1, but in Turing machines a tape cell could hold any number of symbols. I'm having trouble why the base is '2' and not something like 'b' where 'b' is the number of types of symbols of the Turing machine tape.

  • $\begingroup$ That is the worst case. As is also shown by the use of O notation. It is commonly referred to the encoding in the CLRS. Since every character can be encoded in a minimum of 2 characters. If you encode using only one than you will have a linear complexity in input length rather than the logarithmic complexity the binary encoding offers. Which when applied to a linear problem will give a theoretical exponential complexity. Please refer to CLRS, Introduction to Algorithms part on NP completeness for better explanation. $\endgroup$ – anon Jan 1 '19 at 23:16

why the base is '2' and not something like 'b' where 'b' is the number of types of symbols of the Turing machine tape?

Because it does not matter in the sense that $2^{O(f(n))} = b^{O(f(n))}$ for any positive $b > 1$.

Using the popular set-theoretic understanding of the big $O$-notation, we have $$\begin{align} 2^{O(f(n))}&=\{2^{g(n)}\mid g(n)\in O(f(n))\} \\ &=\{\left(b^{\log_b2}\right)^{g(n)}\mid g(n)\in O(f(n))\} \\ &=\{b^{h(n)}\mid \exists g(n),\ h(n)= (\log_b2)g(n),\ g(n)\in O(f(n))\} \\ &=\{b^{h(n)}\mid h(n)\in O(f(n))\} \\ &=b^{O(f(n))}\end{align}$$

By the way, there is no need to assume $f(n)\ge n$. For example, all above hold when $f(n) = \lceil\sqrt n\rceil$ or $f(n) = \lceil\log_2n\rceil$.


Because an exponential function to any base can be expressed in terms of any exponential function of another base, in a way which also happens to make this possible. Namely, for any real number $a > 0$, $a^x = 2^{\lg(a)\ x}$. Thus if you have $a^{O(f(n))}$ it is the same as $2^{\lg(a)\ O(f(n))}$. But a constant multiplying a big-O simply gets absorbed into it, since the whole point of the notation is that it's the shape, not the scale, of the function wrapped by it that counts.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.