Solve the following recurrence relations using backward substution.

a$)x(n)=x(n-1)+n-1$ for $n>0,x(0)=0$

b$)x(n)=x(\frac{n}{3})+n$ for $n>1,x(1)=1$

c$)x(n)=2x(\frac{n}{2})+6$ for $n>1,x(1)=0$

Write the Algorithm for Travel Salesman Problem with its efficiency.

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 algorithm's basic operation is executed.

b$.$ How does this algorithm compare with the straightforward non recursive algorithm for computing this sum?

$9.$ Find $GCD(46,290)$ by applying Euclid's algorithm.

$10.$ For each of the following functions $C(n),$ indicate how much the Running

Time $T(n)$ will change its input is increased triple fold.

$($a$)\sqrt[\phantom{2}]{?}{n}^3$

$($b$)lo{g}_{2}n$

$($c$)3^n$

d$)$

$n^4$