Font size
WorksheetsAlgorithm analysis: divide & conquer theory
Total questions: 10
Worksheet time: 5mins
Can we divide problem into more than 2 sub problems?
Yes
No
Divide & Conquer strategy is a guaranteed to be better than brute force.
true
false
Strategy is a (a) to solve a problem.
In divide & conquer strategy, problems are solved (a) .
To use divide & conquer strategy, we must know how to ________ our problem and ________ the solutions.
(a)
When using technique 'A', we divide a problem into subproblems. When the solution to each subproblem is ready, we 'combine' the results from the subproblems to solve the main problem. What might be the 'A' here?
Divide Technique
Divide and Conquer Technique
Split and Combine Technique
Combine Technique
divide and conqure approach solves subproblems recursively.
False
True
What is the time complexity of the Merge Sort algorithm, which is an example of the Divide and Conquer technique, for sorting an array of n elements?
O(n)
O(log n)
O(nlogn)
O( n2 )
Which of the following are the advantages of using the Divide and Conquer technique?
It can reduce the time complexity of an algorithm
It can simplify the implementation of an algorithm
It can reduce the space complexity of an algorithm
It can always guarantee the optimal solution to a problem
Referring to the master theorem –>T(n) = aT(n/b) + f(n), what could be the value for a here?
1
2
3
4
