$3.$ Consider the following recursive algorithm for computing the sum of the first

n cubes: S$($n$)=13+23+...+$ n$3.$

$2\mathrm{.}4$ Mathematical Analysis of Recursive Algorithms $77$

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

a$.$ Set up and solve a recurrence relation for the number of times the algo$-$

rithm$$s basic operation is executed.

b$.$ How does this algorithm compare with the straightforward nonrecursive

algorithm for computing this sum?