what is the recurrence that describe this run time algorithm?

Question

Is the recurrence that describe this run time algorithm is $T(n) = 2(T/2) + n$? Am I correct? and is the base case for this question $T(1) = 1$? What if happens if it is $T(3)$ how do I get the answer?

Answer 1

It should be $T(n) = T(n-1)+n-1,$ $T(1)=1$. For in each subproblem of size $n$, we have a subproblem of size $n-1$ (comparing the numbers $A[1],\ldots A[n-1]$ and linear work ($n-1$ comparisons between elements). It follows that $T(n) = \frac12 (n-1)n + 1$. For clearly $T(1) = \frac12(1-1)\cdot 1+1=1$ and if $T(n) = \frac12 (n-1)n + 1$ for some positive integer $n$, then \begin{align} T(n+1) &= T(n)+n-1\\ &=\frac12(n-1)n + 1 + n\\ &= \frac12 n(n+1) +1, \end{align} so by induction the statement holds for all positive integers $n$.