Explore topic-wise InterviewSolutions in .

Correct choice is (B) 15

Best explanation: The RESULTANT matrix will be of order 3*5 when MULTIPLIED recursively and therefore the matrix will have 3*5=15 ELEMENTS.

Right answer is (b) 2

Best 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.

Right ANSWER is (b) 2

To EXPLAIN: The SECOND CASE of master’s theorem can be extended for a case where f(n) = n^c (log n)^k and the resulting recurrence becomes T(n)= O(n^c (log n))^k+1.

Correct choice is (a) 1

Easiest 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(n^2.7) using master’s theorem first case.

The CORRECT option is (b) 2

Best 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.

Right option is (c) T(n) = O(f(n))

The best I can EXPLAIN: 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)).

The correct choice is (B) T(N) = O(n^c LOG n)

To explain: In second case of master’s theorem the NECESSARY condition is that c = logba. If this condition is TRUE then T(n) = O(n^c log n)

The correct choice is (a) T(N) = O(n^logba)

The best explanation: In FIRST case of master’s theorem the necessary CONDITION is that c < logba. If this condition is true then T(n) = O(n^logba).

The correct answer is (a) SOLVING recurrences

Easy 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.

The correct choice is (a) True

For explanation: Iterative solution to tower of hanoi puzzle also EXISTS. Its APPROACH depends on whether the total numbers of DISKS are even or ODD.

The correct answer is (b) O(2^n)

The EXPLANATION is: TIME COMPLEXITY of the problem can be found out by solving the recurrence RELATION: T(n)=2T(n-1)+c. Result of this relation is found to be equal to 2^n. It can be solved using substitution.

Right option is (B) O(n)

EASY EXPLANATION - The time complexity will be O(n) when BINARY search is applied on a linked list.

Correct answer is (a) No

For EXPLANATION: Since linked list doesn’t ALLOW RANDOM access, binary search cannot be APPLIED on a sorted linked list in O(Logn) TIME.

Right ANSWER is (c) O(logn)

The best I can explain: The time COMPLEXITY of the above recursive IMPLEMENTATION of binary SEARCH is O(logn).

Right CHOICE is (d) No method is defined to search for an ELEMENT in the given array

Easy EXPLANATION - ITERATIVE linear search, RECURSIVE linear search and Recursive binary search can be applied to search for an element in the above given array.

The correct answer is (a) Iterative linear SEARCH

Explanation: Iterative linear search can be USED to search an ELEMENT in an unsorted ARRAY.

Note: Binary search can be used only when the array is SORTED.

The correct answer is (C) Both recursion and ITERATION

The best I can explain: Both recursion and iteration can be used to FIND the largest and smallest element in an ARRAY.

Right choice is (B) O(n^2)

The BEST I can EXPLAIN: 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(n^2).

The correct answer is (a) Selection sort

Easiest 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.

Correct option is (a) True

Explanation: Since The Coppersmith-Winograd algorithm multiplies the matrices in O(n^2.37) time. The time COMPLEXITY of RECURSIVE MULTIPLICATION of two square matrices by Strassen’s Method is found to be O(n^2.80). THEREFORE, Coppersmith-Winograd algorithm better than Strassen’s algorithm in terms of time complexity.

Correct choice is (b) selection SORT

For explanation: Selection sort is not an adaptive sorting algorithm. 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(n^2).

Right option is (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.

The correct option is (d) it requires only n swaps under any condition

For 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.

The correct choice is (b) O(n^2.37)

To explain: The Coppersmith-Winograd ALGORITHM MULTIPLIES the MATRICES in O(n^2.37) time. Several IMPROVEMENTS have been MADE in the algorithm since 2010.

Correct answer is (a) True

The EXPLANATION is: Given that B=C, so the two MATRIX can be RECURSIVELY multiplied. Therefore, the order of the Matrix X*Y is A*D.

Correct option is (c) O(n^3)

BEST explanation: The time COMPLEXITY of recursive multiplication of two square MATRICES by the Divide and Conquer method is found to be O(n^3) since there are total of 8 recursive calls.

Correct choice is (B) 7

The best EXPLANATION: For the MULTIPLICATION two square matrix recursively using Strassen’s Method, there are 7 recursive calls performed for high TIME complexity.

The correct option is (a) O(n^log7)

The BEST I can EXPLAIN: The time COMPLEXITY of recursive multiplication of two square matrices by Strassen’s Method is found to be O(n^log7) SINCE there are TOTAL 7 recursive calls.

Correct choice is (d) 8

For explanation: For the multiplication two square matrix recursively USING Simple DIVIDE and Conquer METHOD, there are 8 recursive calls PERFORMED for high time complexity.

The CORRECT option is (c) 1100100

For explanation: 100 = 64 + 32 + 4 = 2^6 + 2^5 + 2^2 = 1100100.

The correct option is (b) 1

The BEST I can explain: The SUM of DIGITS will be minimum for the number 1000 and the sum is 1.

Correct choice is (b) O(N)

The best EXPLANATION: The time complexity of the above CODE used to reverse a STRING is O(n).

Right option is (B) Euclid’s Algorithm

The best 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.

The correct answer is (a) a

For explanation: Since the lcm FUNCTION FOLLOWS ABSORPTION laws so lcm (a, gcd (a, B)) equal to a.

The correct choice is (a) True

Easy EXPLANATION - The LCM function is an associative function as lcm (a, lcm (B, c) is EQUAL to lcm (lcm (a, b), c).

The correct answer is (d) lcm (lcm (a, b), c)

For EXPLANATION: SINCE LCM function follows ASSOCIATIVITY, HENCE lcm (a, lcm (b, c) is equal to lcm (lcm (a, b), c).