Set up time complexity for the following programs and solve the following recur

rences:

L $=($l$1,$l$2...$ln$)$ is a list of size n

SolveProb$($L$)$

$\{$

If n $>1\{$

SolveProb$($L$1=($l$1,$l$2...$ln$1))$

SolveProb$($L$2=($l$2,$l$3...$ln$))$

SolveProb$($L$3=($l$2,$l$3,...$ln$1))\}$

$\}($i$)$ Set up time complexity for the following programs and solve the following recur$-$

rences:

$L=(l_1,l_{2}dots{l}_n)$ is a list of size $n$

SolveProb$($L$)$

$\{$

If

SolveProb $(L_1=(l_1,l_{2}dots{l}_{n-1}))$

SolveProb $(L_2=(l_2,l_{3}dots{l}_n))$

$\{$:SolveProb$(L_3=(l_2,l_3,dots{l}_{n-1}))\}$

$\}$

$($ii$)$ Solve the following recurrence:

$T(n)=4T(n-1)+2^n,n>0$

with $T(0)=1.$

$($iii$)$ Solve

$T(n)=8T(n-1)-16T(n-2),n>1$

with $T(0)=2,T(1)=10$

Use the recursion tree method to solve

$T(n)=T(n-c)+T(c)+f(n)$

where $c=$ is a constant and $T(c)=c$

$($a$)f(n)=loglogn$

$($b$)f(n)=\sqrt[\phantom{2}]{n}$

Repeat the above for the recurrence

$T(n)=2T(\frac{n}{2})+f(n)$

where $T(1)=1($assume $n$ is a power of $2).$

Suppose student Anil Bright wants to determine the maximum valued sub$-$sequence

problem by partitioning the sequence into three equal parts. Help him by designing

the algorithm and analyze it$.$

Fill in details and analyse the following version of Quicksort.

K$-$QuickSort $(n)$ :

$($i$)$ Partition the numbers into $k$ parts using $k$ partition items.

$($ii$)$ Sort the parts recursively.

For the analysis, assume that the $n$ number are partitioned into $k($roughly$)$ equal

parts

Suppose we have an array $A=[a_1,\frac{1}{a_2}dots{a}_n]$ of $n$ values and we are required to

compute ${\displaystyle \underset{i}{\overset{?}{}}},j{a}_i**a_j**(j-i{)}^2.$ Design an algorithm for this problem?