Algorithm analysis: divide & conquer theory

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 ______ to solve a problem.

In divide & conquer strategy, problems are solved _________ .

To use divide & conquer strategy, we must know how to ________ our problem and ________ the solutions.

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)

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