$1.$ Consider the following iterative function:

int square$($int n$)\{$

int result $=0$;

for $($int i $=1$; i $<=$ n; i$++)$

result $+=2*$ i $-1$;

return result;

$\}$

Rewrite the function square using recursion and add preconditions and postconditions as

comments. Then prove by induction that the recursive function you wrote is correct.

$2.$ Suppose the number of steps required in the worst case for two algorithms are as follows:

$$ Algorithm $1$: f$($n$)=3$n

$2+9$

$$ Algorithm $2$: g$($n$)=51$n $+17$

Determine at what integer value of n$,$ algorithm $2$ becomes more efficient than algorithm

$1$