Since insertion into a (balanced) BST takes Θ(log n)
, and the tree starts off with 0
nodes, then 1
node, then 2
, etc., we get a running time of:
Θ(log 1 + log 2 + ... + log n)
From here, we can just directly say the running time is Θ(n log n)
since: (related post)
log 1 + log 2 + ... + log n <= log n + log n + ... + log n
= n log n
log 1 + ... + log n/2 + ... + log n >= log n/2 + ... + log n
>= log n/2 + ... + log n/2
= n/2 log (n/2)
This is also related to tree sort.
We can actually prove that we can't do this faster than Θ(n log n)
:
It's been proven to require at least Θ(n log n)
time on average to sort (using a comparison-based algorithm).
Since we can iterate over a BST in Θ(n)
, we can directly infer that we need at least Θ(n log n)
time for the insertion.
Note - for a non-balanced BST, the running time would actually be Θ(n²)
, since the worst-case insertion time for an unbalanced BST is Θ(n)
, so we have:
Θ(1 + 2 + ... + n) = Θ(n(n+1)/2) = Θ(n²)