I've encountered this question on an informal test.

T(n) is a reccurance relation

If the time complexity of an algorithm with input size of n is defined as:

T(1)=A

T(n)=T(n-1) B when n>1

Where A and B are positive constant values.

Then the algorithm design pattern is best described as:

---

A. Decrease and Conquer - Correct answer

B. Divide and Conquer

C. Quadratic

D. Generate and Test

T(n) converges down to T(n) = nB A -> O(n)

1. What's the difference between answer A and B?

2. Why is the answer Decrease and Conquer?

CodePudding user response：

From Wiki,

Under this broad definition, however, every algorithm that uses recursion or loops could be regarded as a "divide-and-conquer algorithm". Therefore, some authors consider that the name "divide and conquer" should be used only when each problem may generate two or more subproblems. The name decrease and conquer has been proposed instead for the single-subproblem class.

Now coming to your question:

1. What's the difference between answer A and B?

A is used for algorithms which generates single subproblem, while B is used for algorithms which generate 2 or more subproblems.

2. Why is the answer Decrease and Conquer?

From the given problem: T(n)=T(n-1) B, we are creating a single sub-problem i.e. T(n-1) hence we identify the algorithm as decrease and conquer.