2013 May 15,
Carleton College, Spring 2013
Prof. Joshua R. Davis, , CMC 325, x4473
A. Let f(n) be a function that limits to infinity as n goes to infinity. Prove that O(2f(n)) is a proper subset of 2O(f(n)).
When we were studying computability, we showed that a k-tape Turing machine is equivalent to a single-tape Turing machine. We actually made two or three arguments for this fact. One argument worked by interleaving the k tapes on the single tape. Another argument worked by enlarging the tape alphabet to consist of k-tuples of tape symbols. Now that we're studying complexity, we've shown that the interleaving approach leads to (at worst) a quadratic blowup in running time.
B. Does the k-tuple approach also lead to a quadratic blowup in running time?