Consider the following recursive algorithm. Algorithm Q(n) //Input: A positive i
ID: 3629270 • Letter: C
Question
Consider the following recursive algorithm.
Algorithm Q(n)
//Input: A positive integer n
if n = 1 return 1
else return Q(n - 1) + 2 * n - 1
a. Set up a recurrence relation for this function’s values and solve it to determine what this algorithm computes.
b. What is the basic operation of this algorithm? Set up a recurrence relation for the number of basic operations made by this algorithm and solve it.
-----------------------------------
I already got part a. but if someone can help me with part b, I would appreciate it!
Explanation / Answer
b)
The basic operations of the algorithm are multiplication and addition.
The recurrence relation for the number of multiplications made by this algorithm is M(n)=M(n-1)+1 for n>1.
The initial condition is M(1)=0.
M(n)=M(n-1)+1
M(n-1)=M(n-2)+1
M(n-2)=M(n-3)+1
By substituting the values of M(n-1) and M(n-2) in M(n),
M(n)=M(n-1)+1
M(n)=(M(n-2)+1)+1
M(n)=((M(n-3)+1)+1)+1
M(n)=M(n-3)+3
For n=4, M(n)=M(1)+3 which is equal to n-1.
By solving the recurrence relation using backward substitution, the number multiplications needed is n-1.
The recurrence relation for the number of additions or subtractions made by this algorithm is C(n)=C(n-1)+3 for n>1.
The initial condition is C(1)=0.
C(n)=C(n-1)+3
C(n-1)=C(n-2)+3
C(n-2)=C(n-3)+3
By substituting the values of C(n-1) and C(n-2) in C(n),
C(n)=C(n-1)+3
C(n)=(C(n-2)+3)+3
C(n)=((C(n-3)+3)+3)+3
C(n)=C(n-3)+9
If the value of n is 5,
C(5)=C(n-4)+12
C(5)=C(1)+3(n-1)
C(5)=3(n-1)
By solving the recurrence relation using backward substitution, the number additions or subtractions needed is 3(n-1).
If the number of subtractions is ignored, then the recurrence relation is C(n)=C(n-1)+2. The number of additions is 2(n-1).