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

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

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.$$
• You can safely use floor twice. The additional element in case of odd numbers is handled by the constant term $+c$. Each invocation of recursive algorithm constructs a subtree and splits the sorted array into 3 parts: one of at most $\lfloor n/2 \rfloor$ elements, a "middle" element that will become the root of the subtree, and a final part of at most $\lfloor n/2 \rfloor$ elements. Jun 9 '20 at 21:22