(a) Decide whether each of the following expressions are true or not. Answer yes or no....
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
(a) Decide whether each of the following expressions are true or not. Answer yes or no. In any case where it is not true, provide the actual O-complexity. (i) log n = O(n!) (ii) 10! = O(log n) (iii) 4n 7 + 3n 3 = O(n 10) (iv) 2n 3+2n 2 = O(n 2) (v) 4 n = O(5n) (b) Let ECFG = {hGi | G is a CFG and L(G)=0}. Consider the a Turing machine T for deciding ECFG, which is described as follows. T = "On input hGi, where G is a CFG: 1. Mark all terminal symbols in G. 2. Repeat until no new variables get marked: . 3. Mark any variable A where G has a rule A → U1U2 Uk and each symbol U1, ..., Uk has already been marked. 4. If the start variable is not marked, accept; otherwise, reject." Let n be the total length of the input (that is, of the encoding of G). What is the time complexity of T? Explain your answer. (a) Decide whether each of the following expressions are true or not. Answer yes or no. In any case where it is not true, provide the actual O-complexity. (i) log n = O(n!) (ii) 10! = O(log n) (iii) 4n 7 + 3n 3 = O(n 10) (iv) 2n 3+2n 2 = O(n 2) (v) 4 n = O(5n) (b) Let ECFG = {hGi | G is a CFG and L(G)=0}. Consider the a Turing machine T for deciding ECFG, which is described as follows. T = "On input hGi, where G is a CFG: 1. Mark all terminal symbols in G. 2. Repeat until no new variables get marked: . 3. Mark any variable A where G has a rule A → U1U2 Uk and each symbol U1, ..., Uk has already been marked. 4. If the start variable is not marked, accept; otherwise, reject." Let n be the total length of the input (that is, of the encoding of G). What is the time complexity of T? Explain your answer.
Expert Answer:
Answer rating: 100% (QA)
a are the answers for each expression i No log n On is not true The actual complexity is Olog n ii Yes 10 Olog n is true iii No 4n7 3n3 On10 is not true The actual complexity is On7 iv Yes 2n3 2n2 On2 ... View the full answer
Related Book For
Posted Date:
Students also viewed these accounting questions
-
Answer the following questions related to a companys activities for the current year: 1. After using an expected useful life of 20 years and no salvage value to depreciate its office equipment over...
-
Answer the following questions related to these goods: apples, Stephen King novels, street lighting on campus, and NPR radio broadcasts. a. Which of these goods are non-rival? b. Which of these goods...
-
Answer the following questions related to Dubois Inc. (a) Dubois Inc. has $600,000 to invest. The company is trying to decide between two alternative uses of the funds. One alternative provides...
-
How does a project manager calculate start and finish times?
-
Zelo, Inc. stock has a beta of 1.23. The risk-free rate of return is 4.5% and the market rate of return is 10%. What is the amount of the risk premium on Zelo stock? A. 4.47% B. 5.50% C. 5.54% D....
-
Cat Fancy, Inc., has provided the following information from its most current financial statements. Total revenue........................................................................... $150,000...
-
Distinguish between environmental impact, environmental quality and environmental effect. How are these related to life-cycle assessment?
-
For each of the following companies, specify whether each company would be more likely to use job costing or process costing. a. Aircraft builder b. Hospital c. Cement plant d. Dentist e. Advertising...
-
5/6 10 5 10 5. /2~ 2/3 7/6 4/3 /3 /6 5/3 53/2 10 Plot points associated with r = 0. Input: Angle Theta Output: Radius (defined by function above) 0 12 66 6 5 10 4 11/6 Em 3 5 12 52 B|2 12 20 3 4 5 6...
-
State the predicted height, taken from your graph, of the ping pong ball bounce when dropped from 4 m. Then draw a sketch of the ping pong ball at the top of its bounce (maximum height) and give your...
-
The Department of Budget and Management (DBM), upon approval and issuance of the General Appropriations. released the following for Agency X on January 2, 2020: General Appropriations: Personnel...
-
Despite their importance, D&I strategies are difficult to implement, and they often do not deliver the benefits they promise. Why is this the case? Many companies underestimate the time and effort...
-
Read the article: Fallon, Nicole (September 18, 2020) Seven Labor Laws You Might be Breaking ) Business News Daily Seven Labor Laws You Might Be Breaking Write a one to two page paper in WORD which...
-
Do you agree that safety professionals need to be up to date with both OSHA and local codes and use care not to be wasteful of recourses? Is that how you would handle the overlap?
-
Sharing your thoughts on professional communication. That can be often overlooked! How would you describe appropriate language for workplace and academic writing?
-
Justin and Lauren are equal partners in the PJenn Partnership. The partners formed the partnership seven years ago by contributing cash. Prior to any distributions, the partners have the following...
-
1. The advantage of game theory is that it allows us to focus on _____ a. each firms incentive to charge a higher price for its product. b. the relationship between business and ethics in a market....
-
Baxter, Inc., owns 90 percent of Wisconsin, Inc., and 20 percent of Cleveland Company. Wisconsin, in turn, holds 60 percent of Clevelands outstanding stock. No excess amortization resulted from these...
-
The auditor determines that each of the following objectives will be part of your audit of Farmington Inc: 1. Establish that the client has rights to the recorded inventories. 2. Establish the...
-
Charles is at a neighbourhood Christmas party with several of his roommates. Over a few beers, Charles gets into a conversation with a neighbour, William, about mutual acquaintances. Charles is a...
-
Steven Erasmus has had difficulties throughout the audit of Kingston Catering. The company is a long-standing client of the audit firm and there have been no problems in the past. However, four...
-
Determine the state of stress at point \(A\) on the cross section of the post at section \(a-a\). Indicate the results on a differential element at the point. 5ft 400 lb a 1.5 ft 300 lb a 2.5 in. 2...
-
The rod has a diameter of \(40 \mathrm{~mm}\). Determine the stress components that act at point \(B\), and show the results on a volume element located at this point. 1500 N 300 mm 600 N 100 Nm 800...
-
Determine the state of stress at point \(B\) on the cross section of the post at section \(a-a\). Indicate the results on a differential element at the point. 5 ft 400 lb 1.5 ft 300 lb a a 2.5 in.- 2...
Study smarter with the SolutionInn App