Consider the following algorithm. A is an array of size n. Algorithm rec(n)
In: Integer value n.
if n = 0 then return 1 else {
i ← rec(n - 1) A[n] ← i return i
}
a) Write a recurrence equation for the time complexity of this algorithm.
b) Solve the above recurrence equation by repeated substitution and give the order of the time complexity.