(a) Decide whether each of the following expressions are true or not. Answer yes or no....

  

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.

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