sider the following program segment.$//$ Input: A positive integer n

while p s n do

return p$[2$ points$]$ What is the basic operation? How many times it is executed for n$=10?$

basic operation is the addition at line $5$

it is execubed times becanse $p$ is increased

b$)2$ in each iteration

$[3$ points$]$ What is the efficiency of the algorithm? Show your work in detail.

$1+2kn$

$k\frac{n-1}{2}$

$k=\frac{1}{2}n-\frac{1}{2}$

$=k+1$

$=\frac{1}{2}n-\frac{1}{2}+1$

$=\frac{1}{2}n+\frac{1}{2}in(n)(2)$ Consider the following recursive algorithm.$//$ Imput: A positive integer n return $1$ return $7**$Q$($n$-1)+2*$n$($a$)[1$ point$]$ What is the basic operation?

muttiplication

$($b$)[2$ points$]$ Write the recurrence relation for the time complexity $T(n).$ Show your work in detai

dir$(1)=0,$prer$(n)=0,$post$(n)=1,$

$T(n)=\{\begin{array}{cc}0,& (n=1)\end{array}$

$0+T(n-1)+1,(n>1)$

$T(1)=0$

$T(n)=T(n-1)+1$

$($c$)[2$ points$]$ Find the solution of $T(n).$

$T(1)=0$

$T(n)=T(n-1)+1$

$T(n)=T(n-1)+1$

$=T(n-2)+1+1$

$=T(n-3)+1+1+1$

vdotsT$(n-k)+k$

$stcp(k)=T(n)$

Draft

$\{[T(n)=T(n-1)+1],[T(n-1)=T(n-2)+1],[T(n-2)=T(n-3)+]\}$

until $=>T(u-k)=T(1)$

$n-k=1=>$:$.k=n-1$

$T(n)=T(1)+n-1$

$T(n)=n-1,in(n)$

Note: please explain how to solove these questions in detailed, and what should I keep in mind while solving them