jeudi 14 juillet 2022

How to determine design pattern from time complexity

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?

Aucun commentaire:

Enregistrer un commentaire