How to determine design pattern from time complexity

user_14141223 0
Viewed 42

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?

algorithm design-patterns
1 Answers

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(Decrease and Conquer) is used for algorithms which generates single subproblem, while B(Divide and Conquer) is used for algorithms which generate 2 or more subproblems.

  1. 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.

user_99289080
Related