0

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.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Taking1n1
  • 145
  • 1
  • 7
  • 7
    I'm voting to close this question as off-topic because it is a theoretical question not a programming question. – Raymond Chen Jan 01 '19 at 20:57
  • 1
    You should ask this on the computer science stack exchange. – Yakov Dan Jan 01 '19 at 20:59
  • 1
    Also posted at [Computer Science Stack Exchange](https://cs.stackexchange.com/questions/102260/if-a-non-deterministic-turing-machine-runs-in-fn-space-then-why-does-it-run-i). Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068). Each community should have an honest shot at answering without anybody's time being wasted. If you don't get a satisfying answer after a week or so, you may flag to request migration. Or you can delete the question on one site and then post to another site. – burnabyRails Jan 02 '19 at 05:56

1 Answers1

4

The important detail here is that the runtime is 2O(n) rather than O(2n). In other words, the runtime is "two raised to the power of something that's O(n)," rather than "something that's on the order of 2n." That's a subtle distinction, so let's dissect it a bit.

Let's consider the function 4n. This function is not O(2n), because 4n outgrows 2n in the long run. However, notice that 4n = 22n, and since 2n = O(n) we can say that 4n = 2O(n).

Similarly, take bn for any base b. If b > 2, then bn is not O(2n). However, we do have that

bn = 2(lg b) n = 2O(n)

because (lg b) n = O(n), since (lg b) is just a constant factor.

It is definitely a bit weird that O(2n) is not the same 2O(n). The idea of using big-O notation in exponents is somewhat odd the first time you see it (for example, nO(1) means "something bounded by a polynomial"), but you'll get used to it with practice.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065