Question $2$

Given the following algorithm

foo $($n$)$

if $n1$

return $1$

else

$x=f(n-1)$

for $i=1$ to $n$

$x=x+i$

return $x$

Determine the asymptotic running time. Assume that addition can be done

in constant time.

$(n^2)$

$(2^n)$

$O(n)$

$(n)$