(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?
-
1. Pick any two of the trends described in this chapter, and discuss how Hersheys values result in positioning the company to use those trends to its advantage. 2. Besides the mentorship program, how...
-
The Sarbanes-Oxley Act requires that the CEO (chief executive officer) and CFO (chief financial officer) of publicly traded corporations include statements of personal certification in the...
-
What should you do if you think that a bill is wrong or want more information about it? How should your creditor respond to your attempt to resolve the situation?
-
The following are misstatements that might be found in the client's year-end cash balance (assume that the balance sheet date is June 30): 1. The outstanding checks on the June 30 bank reconciliation...
-
?Jim's Espresso expects sales to grow by 9.6% next year. Assume that? Jim's pays out 88.1% of its net income. Use the following statements (see attachment) and the percent of sales metho...
-
Prevosti Farms and Sugarhouse pays its employees according to their job classification. The following employees make up Sugarhouse's staff: Employee Number Name and Address Payroll information...
-
You are given: x 60 828 61 62 63 64 65 66 67 4 99,999 88,888 77,777 66,666 55,555 44,444 33,333 22,222 Calculate assuming a uniform distribution of deaths over each year of age
-
Longman, Inc. manufactures lead crystal glasses. The standard direct labor time is \(1 / 5\) hour per glass, at a price of \(\$ 14\) per hour. The actual results for the production of 7,000 glasses...
-
From the viewpoint of a stockholder, which of the following relationships do you consider of least significance? a. The return on assets consistently is higher than the industry average. b. The...
-
In each of the past five years, the net sales of Plaza Co. have increased at about half the rate of inflation, but net income has increased at approximately twice the rate of inflation. During this...
-
Longman, Inc. is a manufacturer of lead crystal glasses. The standard materials quantity is 1 pound per glass at a price of \(\$ 0.40\) per pound. The actual results for the production of 7,000...
-
Which of the following usually is least important as a measure of short-term liquidity? a. Quick ratio. b. Debt ratio. c. Current ratio. d. Cash flows from operating activities.
-
Warner Company's year-end unadjusted trial balance shows accounts receivable of $105,000, allowance for doubtful accounts of $660 (credit), and sales of $340,000. Uncollectibles are estimated to be...
-
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...
-
B Croft has a job as a car salesman. He is paid a basic salary of 200 per month, with a commission extra of 2% on the value of his car sales. During the month of April 19X6 he sells 30,000 worth of...
-
A R Kennedy is a security van driver. He has a wage of 200 per week, plus danger money of 2 per hour extra spent in transporting gold bullion. During the week ended 15 June 19X6 he spends 20 hours...
-
T Penketh is an accountant with a salary of 2,000 per month plus bonus, which for May 19X6 was 400. He pays superannuation contributions of 5% of gross pay, and these are allowed as reliefs against...
Study smarter with the SolutionInn App