Proving building a balanced BST out of sorted array is $\Theta(n)$

Question

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).

Answer 1

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 > 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>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. $$