410+ Design and Analysis of Algorithms Solved MCQs

1.

Recursion is similar to which of the following?

A. switch case
B. loop
C. if-else
D. if elif else
Answer» B. loop
Explanation: recursion is similar to a loop.
2.

Recursion is a method in which the solution of a problem depends on

A. larger instances of different problems
B. larger instances of the same problem
C. smaller instances of the same problem
D. smaller instances of different problems
Answer» C. smaller instances of the same problem
Explanation: in recursion, the solution of a problem depends on the solution of smaller instances of the same problem.
3.

Which of the following problems can’t be solved using recursion?

A. factorial of a number
B. nth fibonacci number
C. length of a string
D. problems without base case
Answer» D. problems without base case
Explanation: problems without base case leads to infinite recursion call. in general, we will assume a base case to avoid infinite recursion call. problems like finding factorial of a number, nth fibonacci number and
4.

In general, which of the following methods isn’t used to find the factorial of a number?

A. recursion
B. iteration
Answer» A. recursion
Explanation: the function counts the number of vowels in a string. in this case the number is vowels is 6.
5.

Which of the following recursive formula can be used to find the factorial of a number?

A. fact(n) = n * fact(n)
B. fact(n) = n * fact(n+1)
C. fact(n) = n * fact(n-1)
D. fact(n) = n * fact(1)
Answer» C. fact(n) = n * fact(n-1)
Explanation: fact(n) = n * fact(n – 1) can be used to find the factorial of a number.
6.

Suppose the first fibonnaci number is 0 and the second is 1. What is the sixth fibonnaci number?

A. 5
B. 6
C. 7
D. 8
Answer» A. 5
Explanation: the sixth fibonnaci number is
7.

Which of the following is not a fibonnaci number?

A. 8
B. 21
C. 55
D. 14
Answer» D. 14
Explanation: 14 is not a fibonnaci number.
8.

Which of the following option is wrong?

A. fibonacci number can be calculated by using dynamic programming
B. fibonacci number can be calculated by using recursion method
C. fibonacci number can be calculated by using iteration method
D. no method is defined to calculate fibonacci number
Answer» D. no method is defined to calculate fibonacci number
Explanation: fibonacci number can be calculated by using dynamic programming, recursion method, iteration method.
9.

Which of the following recurrence relations can be used to find the nth fibonacci number?

A. f(n) = f(n) + f(n – 1)
B. f(n) = f(n) + f(n + 1)
C. f(n) = f(n – 1)
D. f(n) = f(n – 1) + f(n – 2)
Answer» D. f(n) = f(n – 1) + f(n – 2)
Explanation: the relation f(n) = f(n – 1) + f(n – 2) can be used to find the nth fibonacci number.
10.

Which of the following gives the sum of the first n natural numbers?

A. nc2
B. (n-1)c2
C. (n+1)c2
D. (n+2)c2
Answer» C. (n+1)c2
Explanation: the sum of first n natural numbers is given by n*(n+1)/2, which is equal to (n+1)c2.
11.

If GCD of two number is 8 and LCM is 144, then what is the second number if first number is 72?

A. 24
B. 2
C. 3
D. 16
Answer» D. 16
Explanation: as a * b = gcd (a, b) * lcm (a, b). so b = (144 * 8)/72 = 16.
12.

Which of the following is also known as GCD?

A. highest common divisor
B. highest common multiple
C. highest common measure
D. lowest common multiple
Answer» A. highest common divisor
Explanation: gcm (greatest common measure), gcf (greatest common factor), hcf (highest common factor) and hcf (highest common divisor) are also known as gcd.
13.

Which of the following is coprime number?

A. 54 and 24
B. 4 and 8
C. 6 and 12
D. 9 and 28
Answer» D. 9 and 28
Explanation: coprime numbers have gcd 1. so 9 and 28 are coprime numbers. while 54
14.

In terms of Venn Diagram, which of the following expression gives GCD (Given A ꓵ B ≠ Ø)?

A. multiplication of a u b terms
B. multiplication of a ꓵ b terms
C. multiplication of a*b terms
D. multiplication of a-b terms
Answer» B. multiplication of a ꓵ b terms
Explanation: in terms of venn diagram, the gcd is given by the intersection of two sets. so a ꓵ b gives the gcd. while a u b gives the lcm.
15.

What is the GCD according to the given Venn Diagram?

A. 2
B. 3
C. 5
D. 6
Answer» C. 5
Explanation: in terms of venn diagram, the gcd is given by the intersection of two sets. so a ꓵ b gives the gcd. while a u b gives the lcm. so here a ꓵ b is 5.
16.

What is the GCD of a and b?

A. a + b
B. gcd (a-b, b) if a>b
C. gcd (a+b, a-b)
D. a – b
Answer» B. gcd (a-b, b) if a>b
Explanation: as per euclid’s algorithm, gcd (a, b) = gcd (a-b, b) if a > b or gcd (a, b) = gcd (a, b-a) if b > a.
17.

What is the GCD of 48, 18, 0?

A. 24
B. 2
C. 3
D. 6
Answer» D. 6
Explanation: gcd is largest positive integer that divides each of the integer. so the gcd of 48, 18, 0 is 6.
18.

Is 9 and 28 coprime number?

A. true
B. false
Answer» A. true
Explanation: coprime numbers have gcd 1. so 9 and 28 are coprime numbers.
19.

If gcd (a, b) is defined by the expression, d=a*p + b*q where d, p, q are positive integers and a, b is both not zero, then what is the expression called?

A. bezout’s identity
B. multiplicative identity
C. sum of product
D. product of sum
Answer» A. bezout’s identity
Explanation: if gcd (a, b) is defined by the expression, d=a*p + b*q where d, p, q are positive integers and a, b is both not zero, then the expression is called bezout’s identity and p, q can be calculated by extended form of euclidean algorithm.
20.

Is gcd an associative function.

A. true
B. false
Answer» A. true
Explanation: the gcd function is an associative function as gcd (a, gcd (b, c)) = gcd (gcd (a, b), c).
21.

Who gave the expression for the probability and expected value of gcd?

A. james e. nymann
B. riemann
C. thomae
D. euler
Answer» A. james e. nymann
Explanation: in the year 1972, james e. nymann showed some result to show the probability and expected value of gcd.
22.

What is the computational complexity of Binary GCD algorithm where a and b are integers?

A. o (log a + log b)2)
B. o (log (a + b))
C. o (log ab)
D. o (log a-b)
Answer» A. o (log a + log b)2)
Explanation: from the binary gcd algorithm, it is found that the computational complexity is o (log a + log b)2) as the total number of steps in the execution is at most the total sum of number of bits of a and b.
23.

LCM is also called as                  

A. gcd
B. scm
C. gcf
D. hcf
Answer» B. scm
Explanation: gcd (greatest common divisor), gcf (greatest common factor), hcf (highest common factor) is not an alias for lcm. lcm is also called as smallest common multiple(scm).
24.

What is the LCM of 8 and 13?

A. 8
B. 12
C. 20
D. 104
Answer» D. 104
Explanation: 104 is the smallest positive integer that is divisible by both 8 and 12.
25.

Which is the smallest number of 3 digits that is divisible by 2, 4, 8?

A. 100
B. 102
C. 116
D. 104
Answer» D. 104
Explanation: lcm of 2, 4, 8 is 8. so check for the number that is divisible by 8. so 104 is the smallest number that is divisible by 2, 4, 8.
26.

Which of the following is also known as LCM?

A. lowest common divisor
B. least common multiple
C. lowest common measure
D. highest common multiple
Answer» A. lowest common divisor
Explanation: least common multiple is also known as lcm or lowest common multiple.
27.

What is the LCM of two coprime numbers?

A. 1
B. 0
C. addition of two coprime numbers
D. multiplication of two coprime numbers
Answer» D. multiplication of two coprime numbers
Explanation: coprime numbers have gcd 1. while lcm of coprime numbers is the product of those two coprime numbers.
28.

In terms of Venn Diagram, which of the following expression gives LCM (Given A ꓵ B ≠ Ø)?

A. multiplication of a u b terms
B. multiplication of a ꓵ b terms
C. multiplication of a*b terms
D. multiplication of a-b terms
Answer» A. multiplication of a u b terms
Explanation: in terms of venn diagram, the lcm is given by the union of two sets. so a u b gives the lcm. while a ꓵ b gives the gcd.
29.

What is the LCM according to the given Venn Diagram?

A. 2
B. 3
C. 180
D. 6
Answer» C. 180
Explanation: in terms of venn diagram, the lcm is given by the union of two sets. so a u b gives the lcm. so product of all the terms is 180.
30.

What is the lcm (a, b)?

A. a + b
B. gcd (a-b, b) if a>b
C. lcm (b, a)
D. a – b
Answer» C. lcm (b, a)
Explanation: since the lcm function is commutative, so lcm (a, b) = lcm (b, a).
31.

Is 9 and 28 coprime number.

A. true
B. false
Answer» A. true
Explanation: coprime numbers have gcd 1
32.

What is the following expression, lcm (a, lcm (b, c) equal to?

A. lcm (a, b, c)
B. a*b*c
C. a + b + c
D. lcm (lcm (a, b), c)
Answer» D. lcm (lcm (a, b), c)
Explanation: since lcm function follows associativity, hence lcm (a, lcm (b, c) is equal to lcm (lcm (a, b), c).
33.

Is lcm an associative function.

A. true
B. false
Answer» A. true
Explanation: the lcm function is an associative function as lcm (a, lcm (b, c) is equal to lcm (lcm (a, b), c).
34.

What is the following expression, lcm (a, gcd (a, b)) equal to?

A. a
B. b
C. a*b
D. a + b
Answer» A. a
Explanation: since the lcm function follows absorption laws so lcm (a, gcd (a, b)) equal to a.
35.

Which algorithm is the most efficient numerical algorithm to obtain lcm?

A. euler’s algorithm
B. euclid’s algorithm
C. chebyshev function
D. partial division algorithm
Answer» B. euclid’s algorithm
Explanation: the most efficient way of calculating the lcm of a given number is using euclid’s algorithm which computes the lcm in much lesser time compared to other algorithms.
36.

Which of the following methods can be used to find the sum of digits of a number?

A. recursion
B. iteration
C. greedy algorithm
D. both recursion and iteration
Answer» D. both recursion and iteration
Explanation: both recursion and iteration can be used to find the sum of digits of a number.
37.

What can be the maximum sum of digits for a 4 digit number?

A. 1
B. 16
C. 36
D. 26
Answer» C. 36
Explanation: the sum of digits will be maximum when all the digits are 9. thus, the sum will be maximum for the number 9999, which is 36.
38.

What can be the minimum sum of digits for a 4 digit number?

A. 0
B. 1
C. 16
D. 36
Answer» B. 1
Explanation: the sum of digits will be minimum for the number 1000 and the sum is 1.
39.

What is the time complexity of the above code used to reverse a string?

A. copies a string to another string
B. compares two strings
C. reverses a string
D. checks if a string is a palindrome
Answer» D. checks if a string is a palindrome
Explanation: the main purpose of the above code is to check if a string is a palindrome.
40.

Which of the following is the binary representation of 100?

A. 1010010
B. 1110000
C. 1100100
D. 1010101
Answer» C. 1100100
Explanation: 100 = 64 + 32 + 4 = 26 + 25 +
41.

What is the time complexity of the above recursive implementation used to reverse a string?

A. o(1)
B. o(n)
C. o(n2)
D. o(n3)
Answer» B. o(n)
Explanation: the time complexity of the above recursive implementation used to
42.

What is the time complexity of matrix multiplied recursively by Divide and Conquer Method?

A. o(n)
B. o(n2)
C. o(n3)
D. o(n!)
Answer» C. o(n3)
Explanation: the time complexity of recursive multiplication of two square matrices by the divide and conquer method is found to be o(n3) since there are total of 8 recursive calls.
43.

How many recursive calls are there in Recursive matrix multiplication by Strassen’s Method?

A. 5
B. 7
C. 8
D. 4
Answer» B. 7
Explanation: for the multiplication two square matrix recursively using strassen’s method, there are 7 recursive calls performed for high time complexity.
44.

Matrix A is of order 3*4 and Matrix B is of order 4*5. How many elements will be there in a matrix A*B multiplied recursively.

A. 12
B. 15
C. 16
D. 20
Answer» B. 15
Explanation: the resultant matrix will be of order 3*5 when multiplied recursively and therefore the matrix will have 3*5=15 elements.
45.

If Matrix X is of order A*B and Matrix Y is of order C*D, and B=C then the order of the Matrix X*Y is A*D?

A. true
B. false
Answer» A. true
Explanation: given that b=c, so the two matrix can be recursively multiplied.
46.

Is Coppersmith-Winograd algorithm better than Strassen’s algorithm in terms of time complexity?

A. true
B. false
Answer» A. true
Explanation: since the coppersmith- winograd algorithm multiplies the matrices in o(n2.37) time. the time complexity of recursive multiplication of two square matrices by strassen’s method is found to be o(n2.80). therefore, coppersmith-winograd
47.

Which of the following statement is true about stack?

A. pop operation removes the top most element
B. pop operation removes the bottom most element
C. push operation adds new element at the bottom
D. push operation removes the top most element
Answer» A. pop operation removes the top most element
Explanation: as stack is based on lifo(last in first out) principle so the deletion takes place from the topmost element. thus pop operator removes topmost element.
48.

What is the space complexity of program to reverse stack recursively?

A. o(1)
B. o(log n)
C. o(n)
D. o(n log n)
Answer» C. o(n)
Explanation: the recursive program to reverse stack uses memory of the order n to store function call stack.
49.

Stack can be reversed without using extra space by                            

A. using recursion
B. using linked list to implement stack
C. using an extra stack
D. it is not possible
Answer» B. using linked list to implement stack
Explanation: if linked list is used for implementing stack then it can be reversed without using any extra space.
50.

Which of the following is considered as the top of the stack in the linked list implementation of the stack?

A. last node
B. first node
C. random node
D. middle node
Answer» B. first node
Explanation: first node is considered as the top element when stack is implemented using linked list.
51.

What is the time complexity of the program to reverse stack when linked list is used for its implementation?

A. o(n)
B. o(n log n)
C. o(n2)
D. o(log n)
Answer» A. o(n)
Explanation: as a linked list takes o(n) time for getting reversed thus linked list version of stack will also take the same time.
52.

Which of the following takes O(n) time in worst case in array implementation of stack?

A. pop
B. push
C. isempty
D. pop, push and isempty takes constant time
Answer» D. pop, push and isempty takes constant time
Explanation: functions pop, push and isempty all are implemented in constant time in worst case.
53.

What will be the time complexity of the code to reverse stack recursively?

A. o(n)
B. o(n log n)
C. o(log n)
D. o(n2)
Answer» D. o(n2)
Explanation: the recurrence relation for the recursive code to reverse stack will be given by-t(n)=t(n-1)+n.this is calculated to be equal to o(n2).
54.

Which of the following sorting algorithm has best case time complexity of O(n2)?

A. bubble sort
B. selection sort
C. insertion sort
D. stupid sort
Answer» B. selection sort
Explanation: selection sort is not an adaptive sorting algorithm. it finds the index of minimum element in each iteration even if the
55.

Which of the following is the biggest advantage of selection sort?

A. its has low time complexity
B. it has low space complexity
C. it is easy to implement
D. it requires only n swaps under any condition
Answer» D. it requires only n swaps under any condition
Explanation: selection sort works by obtaining least value element in each iteration and then swapping it with the current index. so it will take n swaps under any condition which will be useful when memory write operation is expensive.
56.

What will be the recurrence relation of the code of recursive selection sort?

A. t(n) = 2t(n/2) + n
B. t(n) = 2t(n/2) + c
C. t(n) = t(n-1) + n
D. t(n) = t(n-1) + c
Answer» C. t(n) = t(n-1) + n
Explanation: function to find the minimum element index takes n time.the recursive call is made to one less element than in the previous call so the overall recurrence relation becomes t(n) = t(n-1) + n.
57.

Which of the following sorting algorithm is NOT stable?

A. selection sort
B. brick sort
C. bubble sort
D. merge sort
Answer» A. selection sort
Explanation: out of the given options selection sort is the only algorithm which is not stable. it is because the order of identical elements in sorted output may be different from input array.
58.

What will be the best case time complexity of recursive selection sort?

A. o(n)
B. o(n2)
C. o(log n)
D. o(n log n)
Answer» B. o(n2)
Explanation: selection sort’s algorithm is such that it finds the index of minimum element in each iteration even if the given array is already sorted. thus its best case time complexity becomes o(n2).
59.

Recursive selection sort is a comparison based sort.

A. true
B. false
Answer» A. true
Explanation: in selection sort we need to compare elements in order to find the minimum element in each iteration. so we can say that it uses comparisons in order to sort the array. thus it qualifies as a comparison based sort.
60.

What is the average case time complexity of recursive selection sort?

A. o(n)
B. o(n log n)
C. o(n2)
D. o(log n)
Answer» C. o(n2)
Explanation: the overall recurrence relation of recursive selection sort is given by t(n) = t(n-1) + n. it is found to be equal to o(n2). it is unvaried throughout the three cases.
61.

What is the bidirectional variant of selection sort?

A. cocktail sort
B. bogo sort
C. gnome sort
D. bubble sort
Answer» A. cocktail sort
Explanation: a bidirectional variant of selection sort is called cocktail sort. it’s an algorithm which finds both the minimum and maximum values in the array in every pass.
62.

Which of the following methods can be used to find the largest and smallest element in an array?

A. recursion
B. iteration
C. both recursion and iteration
D. no method is suitable
Answer» C. both recursion and iteration
Explanation: both recursion and iteration can be used to find the largest and smallest element in an array.
63.

What is the number of swaps required to sort the array arr={5,3,2,4,1} using recursive selection sort?

A. 0
B. 1
C. 2
D. 3
Answer» C. 2
Explanation: the first swap takes place between 1 and 5. the second swap takes place between 3 and 2 which sorts our array.
64.

Which of the following methods can be used to find the largest and smallest number in a linked list?

A. recursion
B. iteration
C. both recursion and iteration
D. impossible to find the largest and smallest numbers
Answer» C. both recursion and iteration
Explanation: both recursion and iteration can be used to find the largest and smallest
65.

Which of the following techniques can be used to search an element in an unsorted array?

A. iterative linear search
B. recursive binary search
C. iterative binary search
D. normal binary search
Answer» A. iterative linear search
Explanation: iterative linear search can be used to search an element in an unsorted array.
66.

Consider the array {1,1,1,1,1}. Select the wrong option?

A. iterative linear search can be used to search for the elements in the given array
B. recursive linear search can be used to search for the elements in the given array
C. recursive binary search can be used to search for the elements in the given array
D. no method is defined to search for an element in the given array
Answer» D. no method is defined to search for an element in the given array
Explanation: iterative linear search, recursive linear search and recursive binary search can be applied to search for an element in the above given array.
67.

What is the time complexity of the above recursive implementation of binary search?

A. o(n)
B. o(2n)
C. o(logn)
D. o(n!)
Answer» C. o(logn)
Explanation: the time complexity of the above recursive implementation of binary search is o(logn).
68.

Which of the following methods can be used to search an element in a linked list?

A. iterative linear search
B. iterative binary search
C. recursive binary search
D. normal binary search
Answer» A. iterative linear search
Explanation: iterative linear search can be used to search an element in a linked list.
69.

Can binary search be applied on a sorted linked list in O(Logn) time?

A. no
B. yes
Answer» A. no
Explanation: since linked list doesn’t allow random access, binary search cannot be applied on a sorted linked list in o(logn)
70.

Recursive program to raise an integer x to power y uses which of the following algorithm?

A. dynamic programming
B. backtracking
C. divide and conquer
D. greedy algorithm
Answer» C. divide and conquer
Explanation: the recursive approach uses divide and conquer algorithm as we break the problem into smaller parts and then solve the smaller parts and finally combine their results to get the overall solution.
71.

What is the least time in which we can raise a number x to power y?

A. o(x)
B. o(y)
C. o(log x)
D. o(log y)
Answer» D. o(log y)
Explanation: we can optimize the code for finding power of a number by calculating x raised to power y/2 only once and using it depending on whether y is even or odd.
72.

What is the advantage of iterative code for finding power of number over recursive code?

A. iterative code requires less time
B. iterative code requires less space
C. iterative code is more compiler friendly
D. it has no advantage
Answer» B. iterative code requires less space
Explanation: both iterative and recursive approach can be implemented in log n time but the recursive code requires memory in call stack which makes it less preferable.
73.

Recursive approach to find power of a number is preferred over iterative approach.

A. true
B. false
Answer» B. false
Explanation: the recursive code requires memory in call stack which makes it less preferable as compared to iterative approach.
74.

What is the objective of tower of hanoi puzzle?

A. to move all disks to some other rod by following rules
B. to divide the disks equally among the three rods by following rules
C. to move all disks to some other rod in random order
D. to divide the disks equally among three rods in random order
Answer» A. to move all disks to some other rod by following rules
Explanation: objective of tower of hanoi problem is to move all disks to some other rod by following the following rules-1) only one disk can be moved at a time. 2) disk can
75.

Recurrence equation formed for the tower of hanoi problem is given by                    

A. t(n) = 2t(n-1)+n
B. t(n) = 2t(n/2)+c
C. t(n) = 2t(n-1)+c
D. t(n) = 2t(n/2)+n
Answer» C. t(n) = 2t(n-1)+c
Explanation: as there are 2 recursive calls to n-1 disks and one constant time operation so the recurrence relation will be given by t(n)
76.

Tower of hanoi problem can be solved iteratively.

A. true
B. false
Answer» A. true
Explanation: iterative solution to tower of hanoi puzzle also exists. its approach depends on whether the total numbers of disks are even or odd.
77.

Minimum time required to solve tower of hanoi puzzle with 4 disks assuming one move takes 2 seconds, will be                      

A. 15 seconds
B. 30 seconds
C. 16 seconds
D. 32 seconds
Answer» B. 30 seconds
Explanation: number of moves = 24-1=16- 1=15
78.

Master’s theorem is used for?

A. solving recurrences
B. solving iterative relations
C. analysing loops
D. calculating the time complexity of any code
Answer» A. solving recurrences
Explanation: master’s theorem is a direct method for solving recurrences. we can solve any recurrence that falls under any one of the three cases of master’s theorem.
79.

How many cases are there under Master’s theorem?

A. 2
B. 3
C. 4
D. 5
Answer» B. 3
Explanation: there are primarily 3 cases under master’s theorem. we can solve any recurrence that falls under any one of these three cases.
80.

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)
Answer» B. t(n) = o(nc log n)
Explanation: in second case of master’s theorem the necessary condition is that c = logba. if this condition is true then t(n) = o(nc log n)
81.

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)
Answer» C. t(n) = o(f(n))
Explanation: in third case of master’s theorem the necessary condition is that c > logba. if this condition is true then t(n) = o(f(n)).
82.

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

A. true
B. false
Answer» B. false
Explanation: no we cannot solve all the recurrences by only using master’s theorem. we can solve only those which fall under the three cases prescribed in the theorem.
83.

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
Answer» B. 2
Explanation: the recurrence relation of merge sort is given by t(n) = 2t(n/2) + o(n). so we can observe that c = logba so it will fall under case 2 of master’s theorem.
84.

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
Answer» A. 1
Explanation: the recurrence relation of stooge sort is given as t(n) = 3t(2/3n) + o(1). it is found too be equal to o(n2.7) using master’s theorem first case.
85.

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

A. 1
B. 2
C. 3
D. no case can be extended
Answer» B. 2
Explanation: the second case of master’s theorem can be extended for a case where f(n)
86.

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)
Answer» C. t(n)= o(nc (log n)k+1
Explanation: in the extended second case of master’s theorem the necessary condition is that c = logba. if this condition is true then t(n)= o(nc(log n))k+1.
87.

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
Answer» B. 2
Explanation: the recurrence relation of binary search is given by t(n) = t(n/2) + o(1). so we can observe that c = logba so it will fall under case 2 of master’s theorem.
88.

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
Answer» D. cannot be solved using master’s theorem
Explanation: the given recurrence cannot be solved by using the master’s theorem. it is because in this recurrence relation a < 1 so master’s theorem cannot be applied.
89.

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)
Answer» C. o(m)
Explanation: kmp algorithm is an efficient pattern searching algorithm. it has a time complexity of o(m) where m is the length of text.
90.

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)
Answer» A. o(n + m)
Explanation: z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. it has a time complexity of o(m + n) where m is the length of text and n is the length of the pattern.
91.

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)
Answer» B. o(m)
Explanation: z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. it an auxiliary space of o(m) for maintaining z array.
92.

The naive pattern searching algorithm is an in place algorithm.

A. true
B. false
Answer» A. true
Explanation: the auxiliary space complexity required by naive pattern searching algorithm is o(1). so it qualifies as an in place algorithm.
93.

Rabin Karp algorithm and naive pattern searching algorithm have the same worst case time complexity.

A. true
B. false
Answer» A. true
Explanation: the worst case time complexity of rabin karp algorithm is o(m*n) but it has a linear average case time complexity. so rabin karp and naive pattern searching algorithm have the same worst case time complexity.
94.

Which of the following sorting algorithms is the fastest?

A. merge sort
B. quick sort
C. insertion sort
D. shell sort
Answer» B. quick sort
Explanation: quick sort is the fastest known sorting algorithm because of its highly optimized inner loop.
95.

Quick sort follows Divide-and-Conquer strategy.

A. true
B. false
Answer» A. true
Explanation: in quick sort, the array is divided into sub-arrays and then it is sorted (divide-and-conquer strategy).
96.

What is the worst case time complexity of a quick sort algorithm?

A. o(n)
B. o(n log n)
C. o(n2)
D. o(log n)
Answer» C. o(n2)
Explanation: the worst case performance of a quick sort algorithm is mathematically found to be o(n2).
97.

Which of the following methods is the most effective for picking the pivot element?

A. first element
B. last element
C. median-of-three partitioning
D. random element
Answer» C. median-of-three partitioning
Explanation: median-of-three partitioning is the best method for choosing an appropriate pivot element. picking a first, last or random element as a pivot is not much effective.
98.

Which is the safest method to choose a pivot element?

A. choosing a random element as pivot
B. choosing the first element as pivot
C. choosing the last element as pivot
D. median-of-three partitioning method
Answer» A. choosing a random element as pivot
Explanation: this is the safest method to choose the pivot element since it is very unlikely that a random pivot would consistently provide a poor partition.
99.

What is the average running time of a quick sort algorithm?

A. o(n2)
B. o(n)
C. o(n log n)
D. o(log n)
Answer» C. o(n log n)
Explanation: the best case and average case analysis of a quick sort algorithm are mathematically found to be o(n log n).
100.

Which of the following sorting algorithms is used along with quick sort to sort the sub arrays?

A. merge sort
B. shell sort
C. insertion sort
D. bubble sort
Answer» C. insertion sort
Explanation: insertion sort is used along with quick sort to sort the sub arrays.
Tags
Question and answers in Design and Analysis of Algorithms, Design and Analysis of Algorithms multiple choice questions and answers, Design and Analysis of Algorithms Important MCQs, Solved MCQs for Design and Analysis of Algorithms, Design and Analysis of Algorithms MCQs with answers PDF download