the lower bound time of building a binary search tree by inserting n random elements sequently

Question

The time can be proportional to sum of depth of all nodes.

T(n): the minimal depth sum of all possible BSTs with n elements.

So, T(n) = n-1 + min(T(i)+T(n-1-i)), i from 0 to n-1.

I think that the lower bound should be Θ(n lg n), but I can not prove it.

Answer 1

The lower bound time complexity for building a binary tree from an input stream would be achieved when we can add nodes as high up in the tree as possible (having the least depth). This way the tree remains optimally balanced throughout the process. For instance, we could have this input stream:

4 2 6 1 3 5 7

...which really provides the values for the future tree in level order (breadth-first order).

The time complexity for the individual insertions is linear to the number of nodes to traverse, i.e. the height of the tree at the moment of insertion. This height is O(log𝑛), where 𝑛 is the size of the tree at the moment of insertion.

In general, we have this equality for the combined work of all insertions:

      T_𝑛 = Θ( ∑_𝑖=1..𝑛 log𝑖 )

Which by the logarithm product rule is:

      T_𝑛 = Θ(log(𝑛!))

Which by Stirling's approximation means that:

      T_𝑛 = Θ(𝑛log𝑛)