Divide-and-Conquer algorithms

Question 1

Each node in Recursion tree

Answer 1

Each node is labeled with the size of the problem being solved.

Question 2

Each level is labeled in Recursion tree

Answer 2

Each level is labeled with the number of steps (excluding recursive calls).

Question 3

Total running time of the algorithm in Recursion tree

Answer 3

Total running time of the algorithm is the sum of all the steps in each level.

Question 4

Master Theorem if a = b^c

Answer 4

T(n) = O(n^clogn)

Question 5

Master Theorem if a < b^c

Answer 5

T(n) = O(n^c)

Question 6

Master Theorem if a > b^c

Answer 6

T(n) = O(n^logba)

Question 7

Divide and Conquer Technique

Answer 7

○ Break input into roughly equal halves (Divide).
○ Solve the problem in each of the halves (Conquer).
○ Put together solution to the whole problem (Combine).