Quiz on Divide and Conquer Approach

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)