Proving building a balanced BST out of sorted array is $\Theta(n)$
If you are allowed to use the master theorem then you can immediately conclude that $T(n)=\Theta(n)$ (since $n^{\log_2 2} = n = \omega(1)$).

If you are not allowed to use the master theorem then you can write this recurrence instead:
$$
T(n) \le 2T(\lfloor n/2 \rfloor) + c,
$$
where $c &gt; 0$ is an absolute constant and $T(1) \le c$.

Then you can prove by induction that $T(n) \le 2cn - c$.
The base case is $n=1$ and is trivial since $T(1) \le c = 2cn - c$.
Consider now $n&gt;1$ and suppose that the claim holds up to $n-1$, we will prove that it also holds for $n$:
$$
T(n) = 2T(\lfloor n/2 \rfloor) + c \le 2(2c\lfloor n/2 \rfloor-c) + c \le
2cn - 2c +c=2cn-c.
$$