Question

(Note: "O" stands for Big O notation) prove mathematically that if a Turing Machine runs in...

(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.

Homework Answers

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)

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Prove mathematically that if a Turing Machine runs in time O(g(n)), then it runs in time...
Prove mathematically that if a Turing Machine runs in time O(g(n)), then it runs in time O(h(g(n))+c), for any constant c >= 0 and any functions g(n) and h(n) where h(n) >= n.
Analyze the following code and provide a "Big-O" estimate of its running time in terms of...
Analyze the following code and provide a "Big-O" estimate of its running time in terms of n. Explain your analysis. for ( int i = n; i > 0; i /= 2 ) { for ( int j = 1; j < n; j += 2 ) { for ( int k = 0; k < n; k += 2 ) { ... // constant number of operations } } }
Write a function to check if a machine uses little endian or big endian notation. write...
Write a function to check if a machine uses little endian or big endian notation. write the function checkEndianess(), complete the main function implementation to print the value returned by the function and print if the machine is “Little Endian” or “Big Endian”, compile and run the program. The function checkEndianess() should return the following values: • 0 if the architecture is "Little Endian" • 1 if the architecture is "Big Endian". #include int main() { int check; // Variable:...
#data structures Give the appropriate execution time efficiency of the following array algorithms using Big-O notation....
#data structures Give the appropriate execution time efficiency of the following array algorithms using Big-O notation. Assume the size of the array is n. a)   Linear Search (average case)   ______________________    b)   Binary Search (worst case)       ______________________    c)   Insertion Sort (best case)       ______________________    d)   Insertion Sort (average case)           ______________________    e)   Quick Sort (average case)           ______________________
Are any of the following implications always true? Prove or give a counter-example. a) f(n) =...
Are any of the following implications always true? Prove or give a counter-example. a) f(n) = Θ(g(n)) -> f(n) = cg(n) + o(g(n)), for some real constant c > 0. *(little o in here) b) f(n) = Θ(g(n)) -> f(n) = cg(n) + O(g(n)), for some real constant c > 0. *(big O in here)
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm...
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm that is executed most frequently. Express the number of times it is executed as a function of N. Convert this expression into the Big-O notation. A. For each of the three fragments of code, what is its worst-case time complexity, in the form "O(…)". (Use the given solution to the first problem as a model)                 //----------------- This is a sample problem – solved ------...
This question is already answered before but all of them are wrong. here is the note...
This question is already answered before but all of them are wrong. here is the note from part b) that makes the difference. Please pay attention to the note. [ Note that this cannot be equal to the price at time 5 for the stock in part a, since in part a, D1 = 20, and will grow every year at g = 0.12. ] This note will appear again in part b) and because of this note all the...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number in A and an O(log n)-time computation for each odd number in A. What is the best-case running time of Algorithm X? What is the worst-case running time of Algorithm X? 2. Given an array, A, of n integers, give an O(n)-time algorithm that finds the longest subarray of A such that all the numbers in that subarray are in sorted order. Your algorithm...
in the scheme programming language implement a game of rock paper scissors between a user and...
in the scheme programming language implement a game of rock paper scissors between a user and the computer. Only the following scheme subsets should be used: Special symbols (not case sensitive in our version (R5RS), but is in R6RS): a. Boolean: #t (else) and #f b. Characters: #\a, #\b ... #\Z c. Strings: in double quotes 3. Basic functions: a. quote b. car c. cdr d. c _ _ _ _ r, where each _ is either “a” or “d”...
Write a C++ program that converts time of day from a 24-hour notation to a 12-hour...
Write a C++ program that converts time of day from a 24-hour notation to a 12-hour notation. For example, it should convert 14:25 to 2:25 PM. (A) The user provides input as two integers separated by ‘:’. The following function prototype should capture the user inputs as described below: void input(int& hours24, int& minutes); //Precondition: input(hours, minutes) is called with //arguments capable of being assigned values. //Postcondition: // user is prompted for time in 24 hour format: // HH:MM, where...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT