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
whenn>1
Where
A
andB
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)
-
What's the difference between answer A and B?
-
Why is the answer Decrease and Conquer?
Aucun commentaire:
Enregistrer un commentaire