Algorithm Design And Analysis (Programming): Recursive Algorithm To Determine The Sum Of A Finite Geometric Series Due:

Algorithm Design and Analysis

(Programming): Recursive Algorithm to Determine the Sum of a Finite Geometric Series Due: Feb. 20th, 2022: 11.59 PM A geometric series typically comprises of the sum of an infinite number of terms that have a constant ratio between any two consecutive terms. In this assignment, you will develop arecursive algorithmto determine the sum of a finite geometric series up to power 'n' (shown below) such that the number of multiplications is (n) and the number of additions is (n) as well. S(x,n) = 1 + x + x²+ x³+ + xⁿ Tasks: 1) Write a pseudo code for the recursive algorithm you come up with. 2) Write the recurrence relation to compute S(x, n) as well as the terminating condition. 3) Provide an explanation or a derivation to show that the recursive algorithm of (1) uses the recurrence relation mentioned in (2) and justify that it does work as intended. 4) Write the recurrence relation (as well as the terminating condition) for the number of multiplications M(n) done in (1-2) and solve the recurrence relation to show that M(n) = (n). 5) Write the recurrence relation (as well as the terminating condition) for the number of additions A(n) done in (1-2) and solve the recurrence relation to show that A(n) = (n). 6) Implement the recursive algorithm of (1) in a C++ code that incorporates the recurrence relation of (2) as well as keeps updating the sum S(x, n) for the 'x' and 'n' values input by the user. 'x' and 'n' Values:The 'x' and 'n' values assigned to each student for testing and documenting purposes are as follows:

x	n
3	8
4	8
5	8
6	8
3	7
4	7
5	7
6	7

Submission: 1) The C++ code as a separate .cpp file. 2) A PDF file that comprises of the following: Deliverables corresponding tasks (1) through (5) mentioned above as well as a screenshot of the output of your code for S(x, n) for the x and n values input by the user. Note:You will get a ZERO for the entire assignment if you come up with an algorithm that is NOT recursive.