10: Select the asymptotic worst-case time complexity of the following algorithm:

Question

10: Select the asymptotic worst-case time complexity of the following algorithm: Algorithm input a1, a2, ,a, a sequence of numbers n, the length of the sequence x, a number Output: ?? For i 1 to 3 If (a 0) Retum( "True") End-for End-for Return( False") d. (n2) 7.4 Finite state machines 2:S the sentence that correctly describes the set of strings accepted by the FSM below Start a. The FSM accepts a string x if and only if x contains at least one 0 and at least one 1 b. The FSM accepts a string x if and only if x starts with a 0 and ends with a 1 C. The FSM accepts a string x if and only if the number of 1's in x is odd and the number of O's in x is odd d. The FSM accepts a string x if and only if x contains the pattern 101 somewhere in the string.

Explanation / Answer

a.) Ans. B : In Worst case scenario this code would keep checking through the n number sequence to check if ai is less than x. So the it is of O(n)

b.) Ans. C: in worst case scenario this code have O(n^2) time complexity.

C.) Ans. A : if a string has at least one 0 and at least one 1 then this machine would accept the input. Because 01 and 10 both are smallest valid strings for this machine.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.