Top 150+ Solved Design and Analysis of Algorithms MCQ Questions Answer
Q. What is the result of the recurrences which fall under second 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)
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)
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
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
Q. Which case of master’s theorem can be extended further?
a. 1
b. 2
c. 3
d. no case can be extended
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)
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
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
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)
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)
Q. What is the auxiliary space 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)