cannot be solved using master’s theorem

Design and Analysis of Algorithms MCQ Questions and answers

A

Admin • 802.91K Points
Coach

Q. What is the result of the recurrences which fall under third case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc?

(A) none of the below
(B) t(n) = o(nc log n)
(C) t(n) = o(f(n))
(D) t(n) = o(n2)

A

Admin • 802.91K Points
Coach

Q. We can solve any recurrence by using Master’s theorem.

(A) true
(B) false
(C) ---
(D) ---

A

Admin • 802.91K Points
Coach

Q. Under what case of Master’s theorem will the recurrence relation of merge sort fall?

(A) 1
(B) 2
(C) 3
(D) it cannot be solved using master’s theorem

A

Admin • 802.91K Points
Coach

Q. Under what case of Master’s theorem will the recurrence relation of stooge sort fall?

(A) 1
(B) 2
(C) 3
(D) it cannot be solved using master’s theorem

A

Admin • 802.91K Points
Coach

Q. Which case of master’s theorem can be extended further?

(A) 1
(B) 2
(C) 3
(D) no case can be extended

A

Admin • 802.91K Points
Coach

Q. What is the result of the recurrences which fall under the extended second case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc(log n)k?

(A) none of the below
(B) t(n) = o(nc log n)
(C) t(n)= o(nc (log n)k+1
(D) t(n) = o(n2)

A

Admin • 802.91K Points
Coach

Q. Under what case of Master’s theorem will the recurrence relation of binary search fall?

(A) 1
(B) 2
(C) 3
(D) it cannot be solved using master’s theorem

A

Admin • 802.91K Points
Coach

Q. 7 T (n/2) + 1/n

(A) t(n) = o(n)
(B) t(n) = o(log n)
(C) t(n) = o(n2log n)
(D) cannot be solved using master’s theorem

A

Admin • 802.91K Points
Coach

Q. What is the worst case time complexity of KMP algorithm for pattern searching (m = length of text, n = length of pattern)?

(A) o(n)
(B) o(n*m)
(C) o(m)
(D) o(log n)

A

Admin • 802.91K Points
Coach

Q. What is the time complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?

(A) o(n + m)
(B) o(m)
(C) o(n)
(D) o(m * n)

Show Answer Discuss Share

Design and Analysis of Algorithms MCQs with answers Page - 4

Q. What is the result of the recurrences which fall under third case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc?

Q. We can solve any recurrence by using Master’s theorem.

Q. Under what case of Master’s theorem will the recurrence relation of merge sort fall?

Q. Under what case of Master’s theorem will the recurrence relation of stooge sort fall?

Q. Which case of master’s theorem can be extended further?

Q. What is the result of the recurrences which fall under the extended second case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc(log n)k?

Q. Under what case of Master’s theorem will the recurrence relation of binary search fall?

Q. 7 T (n/2) + 1/n

Q. What is the worst case time complexity of KMP algorithm for pattern searching (m = length of text, n = length of pattern)?

Q. What is the time complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?

Add MCQ in this Category

Browse Categories