NEW
Font size
WorksheetsQuiz on Divide and Conquer Approach
Total questions: 10
Worksheet time: 5mins
What is the first step in the divide and conquer method?
Divide the input into subsets
Combine the solutions of sub-problems
Solve the problem directly
Check the input size of the problem
Which of the following is a classic problem that can be solved using divide and conquer?
Bubble sort
Linear search
Binary search
Finding the greatest common divisor
What is a disadvantage of the divide and conquer algorithm?
It is less efficient than iterative algorithms
It cannot solve large problems
It is not suitable for parallel implementation
It may require more space due to recursion
In the control abstraction of the divide and conquer algorithm, what does the function Is-Small(P) do?
Combines the solutions of sub-problems
Divides the problem into sub-problems
Returns the final solution
Checks if the problem can be solved directly
What is the time complexity of the best-case scenario for binary search?
O(1)
O(n)
O(log n)
O(n log n)
How does the binary search algorithm determine which half of the array to search next?
By using a linear search in both halves
By searching both halves simultaneously
By finding the middle element and comparing
By comparing the search key with the last element
What is the recurrence relation for the worst-case of binary search?
T(n) = T(n/2) + T(n/2)
T(n) = T(n-1) + c
T(n) = 2T(n/2) + c
T(n) = T(n/2) + c
What is the time complexity of the merge sort algorithm?
O(n)
O(n^2)
O(n log n)
O(log n)
In the merge sort algorithm, what is the purpose of the Merge function?
To divide the array into sub-arrays
To find the middle element of the array
To combine two sorted lists into one sorted list
To sort the array in descending order
What is the general form of the recurrence relation for divide and conquer algorithms?
T(n) = k(n)
T(n) = T(n-1) + c
T(n) = T(n/2) + T(n/2)
T(n) = aT(n/b) + h(n)
