Given a binary search tree $T$, we insert $n$ elements, but when the size of tree become doubled then we balance the tree. for example if we insert $2^{k-1}$ element then when the size become to $2^k$ then we balance $T$. what is time complexity insert $n$ items in such tree?
I think be $O(n)$, but when i want draw a such tree i get stuck.
It can't be $O(n)$.
Suppose $n=2^k$,and for given $n$ elements, we inserted $\frac{n}{8}$ and $T$ is balanced. Now suppose you insert next $\frac{n}{8}$, But suppose when you inserted $\frac{1}{2}\frac{n}{8}$ elements that those make a chain with length $O(n)$. So for next $\frac{1}{2}\frac{n}{8}$ elements you maybe have cost $O(n)$ for each insertion. As a result the time complexity of $n$ insertion is $O(n^2)$.