(Solved): (Mathematical Analysis of Recursive Algorithms) 9. Consider the following recursive algorithm for ...

(Mathematical Analysis of Recursive Algorithms) 9. Consider the following recursive algorithm for computing the sum of the first $$n$$ cube: $$S(n)=1^3+2^3+3^3+?+n^3$$. Algorithm $$S(n)$$ //Input: A positive integer $$n$$ //Output: The sum of the first $$n$$ cubes if $$n=1$$ return 1 else return $$S(n?1)+n?n?n$$ Set up and solve a recurrence relation for the number of times the algorithm's basic operation is executed. 10. Write a non-recursive algorithm to do the same operation as in $$Q9$$ computing this function and describe its efficiency.