Find the computational complexity of the given program int seq(int n) 
{
   if(n == 0 || n == 1)
       return n;
   return(seq(floor(n/2)) + seq(ceil(n/2));
}


Find the computational complexity of the above program.

I have tried doing it in the following way:
$$\begin{align*}
T(0) &amp;= 1 \\
T(1) &amp;= 1 \\ 
T(2) &amp;= 2T(1) = 2 \\
T(3) &amp;= T(1) + T(2) = 3 \\
T(4) &amp;= 2T(2) = 4 \\
T(5) &amp;= T(3) + T(2) = 5 \\
&amp;\vdots
\end{align*}$$

So the thing I have observed here was:

$$T(n) = n$$

However I am not sure if this result/approach is even somehow correct, is it? If not can someone show me the way how to approach problems like this one? Thanks
You can analyze using master theorem:
$$T(n) = T(\lfloor\frac{n}{2}\rfloor) + T(\lceil\frac{n}{2}\rceil) + 1$$

As we can suppose $n = 2^k$ and there is no a difference in the asymptotic complexity, We can say $T(n) = 2T(\frac{n}{2})+ 1$.

Hence, from master theorem we can say $T(n) = \Theta(n)$.