Mixing
If a non-deterministic Turing machine runs in f(n) space, then why does it run in 2^O(f(n)) time? [closed]
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.
math big-o complexity-theory turing-machines
edited Jan 1 at 22:28
templatetypedef
266k69676896
asked Jan 1 at 20:55
Taking1n1Taking1n1
5015
closed as off-topic by Raymond Chen, meowgoesthedog, SergGr, James K Polk, OmG Jan 2 at 9:14
- This question does not appear to be about programming within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
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.
math big-o complexity-theory turing-machines
edited Jan 1 at 22:28
templatetypedef
266k69676896
asked Jan 1 at 20:55
Taking1n1Taking1n1
5015
closed as off-topic by Raymond Chen, meowgoesthedog, SergGr, James K Polk, OmG Jan 2 at 9:14
- This question does not appear to be about programming within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.
7
I'm voting to close this question as off-topic because it is a theoretical question not a programming question.
– Raymond Chen
Jan 1 at 20:57
1
You should ask this on the computer science stack exchange.
– Yakov Dan
Jan 1 at 20:59
1
Also posted at Computer Science Stack Exchange. Please do not post the same question on multiple sites. 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 2 at 5:56
add a comment |
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.
math big-o complexity-theory turing-machines
edited Jan 1 at 22:28
templatetypedef
266k69676896
asked Jan 1 at 20:55
Taking1n1Taking1n1
5015
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.
math big-o complexity-theory turing-machines
math big-o complexity-theory turing-machines
edited Jan 1 at 22:28
templatetypedef
266k69676896
asked Jan 1 at 20:55
Taking1n1Taking1n1
5015
edited Jan 1 at 22:28
templatetypedef
266k69676896
asked Jan 1 at 20:55
Taking1n1Taking1n1
5015
edited Jan 1 at 22:28
templatetypedef
266k69676896
edited Jan 1 at 22:28
templatetypedef
266k69676896
edited Jan 1 at 22:28
templatetypedef
266k69676896
266k69676896
asked Jan 1 at 20:55
Taking1n1Taking1n1
5015
asked Jan 1 at 20:55
Taking1n1Taking1n1
5015
asked Jan 1 at 20:55
Taking1n1Taking1n1
5015
5015
closed as off-topic by Raymond Chen, meowgoesthedog, SergGr, James K Polk, OmG Jan 2 at 9:14
- This question does not appear to be about programming within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Raymond Chen, meowgoesthedog, SergGr, James K Polk, OmG Jan 2 at 9:14
- This question does not appear to be about programming within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.
7
I'm voting to close this question as off-topic because it is a theoretical question not a programming question.
– Raymond Chen
Jan 1 at 20:57
1
You should ask this on the computer science stack exchange.
– Yakov Dan
Jan 1 at 20:59
1
Also posted at Computer Science Stack Exchange. Please do not post the same question on multiple sites. 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 2 at 5:56
add a comment |
7
I'm voting to close this question as off-topic because it is a theoretical question not a programming question.
– Raymond Chen
Jan 1 at 20:57
1
You should ask this on the computer science stack exchange.
– Yakov Dan
Jan 1 at 20:59
1
Also posted at Computer Science Stack Exchange. Please do not post the same question on multiple sites. 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 2 at 5:56
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 1 at 20:57
I'm voting to close this question as off-topic because it is a theoretical question not a programming question.
– Raymond Chen
Jan 1 at 20:57
1
1
You should ask this on the computer science stack exchange.
– Yakov Dan
Jan 1 at 20:59
You should ask this on the computer science stack exchange.
– Yakov Dan
Jan 1 at 20:59
1
1
Also posted at Computer Science Stack Exchange. Please do not post the same question on multiple sites. 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 2 at 5:56
Also posted at Computer Science Stack Exchange. Please do not post the same question on multiple sites. 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 2 at 5:56
add a comment |
1 Answer
1
active
oldest
votes
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.
answered Jan 1 at 22:07
templatetypedeftemplatetypedef
266k69676896
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
answered Jan 1 at 22:07
templatetypedeftemplatetypedef
266k69676896
add a comment |
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.
answered Jan 1 at 22:07
templatetypedeftemplatetypedef
266k69676896
add a comment |
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.
answered Jan 1 at 22:07
templatetypedeftemplatetypedef
266k69676896
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.
answered Jan 1 at 22:07
templatetypedeftemplatetypedef
266k69676896
answered Jan 1 at 22:07
templatetypedeftemplatetypedef
266k69676896
answered Jan 1 at 22:07
templatetypedeftemplatetypedef
266k69676896
answered Jan 1 at 22:07
templatetypedeftemplatetypedef
266k69676896
266k69676896
add a comment |
add a comment |
7
I'm voting to close this question as off-topic because it is a theoretical question not a programming question.
– Raymond Chen
Jan 1 at 20:57
1
You should ask this on the computer science stack exchange.
– Yakov Dan
Jan 1 at 20:59
1
Also posted at Computer Science Stack Exchange. Please do not post the same question on multiple sites. 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 2 at 5:56