Consider the following algorithm, Algorithm S(n) :
if(n = 1) { }
else { X 0: S(n - 1) Y(n) }
Let the time complexities of X() and Y(n) are O(1) and O(1 / n) respectively. Derive the recurrence relation for the algorithm.
a) S(n) = S(n - 1) + O(1)
b) S(n) = S(n - 1) + O(1 / n)
c) S(n) = O(n) + O(1)
d) S(n) = O(1) + O(1 / n)
