MCQ - Data Structures - Divide and Conquer Algorithms
* Required
Name
This is a required question
Organisation Name
This is a required question
Full Address
This is a required question
Email-Id (Your score will be emailed to you, so please fill correctly.)
*
This is a required question
Which of the following is true for the equation T(n)=aT(n/2)+O(n) (here log is to the base b)
*
T(n)=O(n^d) if d>log a
T(n)=O(n^d log n) if d^b=log a
T(n)=O(n^log a) if (d<log a)
All the above
This is a required question
When you multiply two n-bit numbers the reccurssion comes down to (after applying Gauss method)
*
T(n)=3T(n/2)+O(n)
T(n)=4T(n/2)+O(n)
T(n)=3T(n/3)+O(n)
T(n)=4T(n/3)+O(n)
This is a required question
If the recurrence relation for a binary search is represented by T(n)=aT(n/b)+O(n^d) then the value of a+b+d is
*
3
4
1
0
This is a required question
The running time of binary search is
*
O(n)
O(nlog n)
O(log n)
O(n^2)
This is a required question
Which of the following is true
*
Merge sort takes T(n)=2T(n/2)+O(n)
Merge sort takes T(n)=3T(n/2)+O(n)
Quick sort takes O(n^2) time in its average case
None of the above
This is a required question
When the merge sort is implemented iteratively then which of the following data structures is used
*
Stacks
Queques
Graphs
Tree
This is a required question
Which of the following is divide and conquer approach algorithm
*
Bubble sort
Insert sort
Quick sort
All of the above
This is a required question
What is the complexity of f(n)=5f(n/2)+3 (apply masters theorem)
*
O(n^log 5) (base is 2)
O(n)
O(n log 2)
O(n^5)
This is a required question
Given a sorted array arr[ ] and a number x counts the occurence of x in arr[ ] the function to implement this logic in an efficient way would take
*
O(log n)
O(n log n)
O(n)
O(n^2)
This is a required question
Never submit passwords through Google Forms.