0
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you! Would it be better to consider one half with floor and the other with ceiling? because the floor might create problems with even number, no? $\endgroup$
    – Combinatoric
    Jun 9, 2020 at 21:19
  • 1
    $\begingroup$ 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. $\endgroup$
    – Steven
    Jun 9, 2020 at 21:22
  • $\begingroup$ Ok, great! thanks! $\endgroup$
    – Combinatoric
    Jun 9, 2020 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.