I'm having hard time proving building a balanced BST out of sorted array is $\Theta(n)$
I got the following formula: $$T(n)=2T(\frac{n}{2})+\Theta(1)$$
I tried to prove it by induction but got stuck with the case in which $n$ is an odd number.
Is there a better way to prove it? Substitution wouldn't be considered a valid proof (I reached the closed formula using substitution of-course).