Time Complexity
Since lookup and insert are our most important operations, let's examine their complexities.
On the last page we saw that the height of the tree can vary a lot, depending on the order of insertion.
- The shortest possible tree (perfectly balanced) has \( \Theta( \log{n} ) \) height. This is the best-case height.
- The tallest possible tree (a stick) has \( \Theta( n ) \) height. This is the worst-case height.
Now think back to our lookup procedure.
Complexity of Lookup
Best-Case Height
The best-case tree shape is perfectly balanced, with \( \Theta( \log{n} ) \) height.
That's still not quite enough information to count operations, though! It also depends on how far down the tree we have to search.
In the worst-case lookup, we have to search all the way to the bottom of tree. That would mean \( \Theta( \mathit{height} ) = \Theta( \log{n} ) \) operations.
On the other hand, in a best-case lookup, our procedure might find the requested key right away (it could be at the root!). That would only be \( \Theta(1) \) operations.
So, we see that the complexity of lookup for a perfectly balanced tree would be no worse than logarithmic, but it could be constant time.
So the most accurate and precise characterization overall would be \( \mathrm{O}( \log{n} ) \).
Worst-Case Height
The worst-case tree shape is a stick, with \( \Theta(n) \) height.
The height alone is not quite enough information to count operations, though! It also depends on how far down the tree we have to search.
In the worst-case lookup, we have to search all the way to the bottom of tree. That would mean \( \Theta(n) \) operations.
On the other hand, in a best case lookup, our procedure might find the requested key right away! That would only be \( \Theta(1) \) operations.
So, we see that the complexity of lookup for a perfectly balanced tree would be no worse than linear, but it could be better.
So the most accurate and precise characterization would be \( \mathrm{O}(n) \).
What Can We Say Overall?
We know that, in the worst of the worst cases, for a terrible tree height and an unlucky choice of key, lookup can take linear time.
We also know that for a lucky key or for a nice tree, it can take less time.
So, the best we could say is that lookup takes \( \mathrm{O}(n) \) time.
Complexity of Insert and Delete
How about insert? Remember that the first step of insert is to find a place for the new key!
The first step of insert is essentially the same steps as lookup to find the insertion position, which we know takes \( \mathrm{O}(n) \) time (i.e., at most linear time).
The second step is just some simple pointer manipulation, which can be done in \( \Theta(1) \) time.
So, overall, we'd have to say that insert takes \( \mathrm{O}(n) \) time.
Delete has essentially the same analysis. First we have to find the node to delete, then we have to do some pointer manipulation. So similarly we would say that delete has \( \mathrm{O}(n) \) time complexity.
This is terrible! I thought we invented BSTs to get away from linear-time lookup/insert!
-
Yes, we did. The linear-time worst case is definitely bad news. But all hope is not lost!
-
How so?
-
Well, we discovered that we can have log-time worst case if the tree is balanced.
So, all we have to do is figure out how to keep the tree balanced!
-
We'll spend the next few lessons discussing clever balancing methods for BSTs.
That sounds so cool! I can hardly wait!!!
-
Okay, great! But first let's wrap up our discussion of basic BSTs.
-
Can we stop with the complexity stuff now? I'm getting a headache!
-
Yes, we're done with that for now. We'll move on to a slightly different topic.
-
Let's head up to the parent page to see our progress and what's next!
(When logged in, completion status appears here.)