Question

(Note: "O" stands for Big O notation)

prove mathematically that if a Turing Machine runs in time O(k(n)), then it runs in time O(h(k(n)) +c), for any constant c ≥ 0 and any functions k(n) and h(n) where h(n) ≥ n.

Answer 1

The solution for the problem is provided below, please comment if any doubts:

• It is given that, a Turing machine is runs in time O(k(n)).
• We need to prove that it runs in O(h(k(n))+c) for any constant c ≥ 0 and any functions k(n) and h(n).
• It is given that h(n) ≥ n, for all positive n.
• The function k(n), is the running time of the Turing machine and it can’t be negative.
• Thus, h(k(n)) ≥ k(n).
• Also c is a positive constant, then: h(k(n))+c≥ h(k(n)) ≥ k(n)
• That is, (h(k(n))+c) ≥ k(n).
• Now according to the definition of big O, if we need to tell that f(n)=O(g(n)), there exist a positive constant “c” such that , f(n)≤ c (g(n)).
• Here we know that, (h(k(n))+c) ≥ k(n)
  • Put c=1.
  • k(n)≤ c (h(k(n))+c)
• That is k(n)=O(h(k(n)) +c).
• That is the running time of the Turing machine, k(n)m is runs at O(h(k(n)) +c).

That is: if a Turing Machine runs in time O(k(n)), then it runs in time O(h(k(n)) +c)