MHB What is the Time Complexity of These Binary Search Tree Functions?

[evinda]

Hello! (Wave)

The following two functions are given and I want to find their time complexity.

function BinarySearchTreeLookUp(key K,pointer R): Type
   if (R==NULL) return nill;
   else if (K==R->key) return R->data;
   else if (K<R->key)
         return(BinarySearchTreeLookUp(K,R->LC));
   else 
         return(BinarySearchTreeLookUp(K,R->RC));

function BinarySearchTreeLookUp(key K,pointer R): Type
   P=R;
   while (P!=NULL && K!=P->key){
            if (K<P->key) P=P->LC;
            else P=P->RC;
   }
   if (P!=NULL) return(P->data);
   else return nill;
}

I think that the time complexity of the first function is $O(h)$ where $\log n \leq h \leq n-1$ and that the time complexity of the second function is $O(n)$. Am I right? (Thinking)

 

[Nono713]

Hello, evinda. Let me quickly preempt all of your follow-up questions by asking you to produce a proof (or a sketch of a proof) that the time complexity of the first algorithm is $O(h)$ where $h$ is presumably the height of the input binary search tree. Then we can check and discuss your proof and hence answer not only your current question but also your real questions, which are "how could we prove it" (because you will already have a proof) and "why does it work" (because you will hopefully understand your own proof). We can discuss the second algorithm once you have finished working on the first one.

If you are somehow only interested in knowing whether your answers are correct, you are right for the first algorithm (assuming $h$ is the height of the tree, which I think is what you meant - please define any variables you use) and completely wrong for the second algorithm.

PS: "nill" is not a word. it's either "null" or "nil" (probably "null" since you are already using it).​

 

[evinda]

Hello, evinda. Let me quickly preempt all of your follow-up questions by asking you to produce a proof (or a sketch of a proof) that the time complexity of the first algorithm is $O(h)$ where $h$ is presumably the height of the input binary search tree. Then we can check and discuss your proof and hence answer not only your current question but also your real questions, which are "how could we prove it" (because you will already have a proof) and "why does it work" (because you will hopefully understand your own proof). We can discuss the second algorithm once you have finished working on the first one.

We have the worst case if either all the keys other than this of the root are greater than this of the root either all the other keys are smaller than this of the root, because in such cases the tree is not balanced.
Then the height of the tree will be equal to the height of the root, that is at the worst case $n-1$.
At the best case, we will have a balanced tree of which we know that the height is $O(\lg n)$.
No matter in which case we are, we cannot have a greater time complexity than $O(h)$ since the path that we will follow cannot be greater than the greatest path from the root to a leaf, that is $O(h)$.
Right? (Thinking)

If you are somehow only interested in knowing whether your answers are correct, you are right for the first algorithm (assuming $h$ is the height of the tree, which I think is what you meant - please define any variables you use) and completely wrong for the second algorithm.

Yes, with $h$ I mean the height of the tree... (Nod)

Is the time complexity of the second algorithm also $O(h)$ ? (Thinking)

 

[Nono713]

We have the worst case if either all the keys other than this of the root are greater than this of the root either all the other keys are smaller than this of the root, because in such cases the tree is not balanced.

This formulation is kind of awkward. A tree has only one root. Perhaps a better way to put is "if every node's key is greater than its parent node's key or if every node's key is smaller than its parent node's key". That way you make sure that the statement holds for every node, not just the root, which identifies the worst case correctly (basically, a linked list). Otherwise your definition above would apply to trees such as these, which are clearly not the worst case:

As you can see, every node other than the root has a smaller key than the root's key, yet the algorithm still performs well. You could also show a picture of an actual worst case tree for illustration if you wanted.

Also, you haven't yet given the proof that the algorithm runs in $O(h)$, so this doesn't explain why it is a worst case. This should be moved after the proof that the algorithm runs in $O(h)$.

At the best case, we will have a balanced tree of which we know that the height is $O(\lg n)$.

Okay, sure. You might give the exact height of a balanced tree, which is $\lceil \log_2 n \rceil$ (or something similar depending on your exact definition of "height"). That way your O-notation is justified. You could show a picture of the best case if you wanted.

Same remark as before, why is this a best case? Should be moved after the proof that the algorithm runs in $O(h)$.

No matter in which case we are

Wait, are you giving a proof only for the best and worst case, or does it work for all $n$? You can't just give a proof for the best and worst case and then interpolate it for every $n$ in between, it doesn't work like that. So get rid of this, replace it by "for any $n$-node binary search tree of some height $h$" and move your best/worst case remarks after this paragraph.

we cannot have a greater time complexity than $O(h)$ since the path that we will follow cannot be greater than the greatest path from the root to a leaf, that is $O(h)$.

Why is that? I mean, yes, okay, but you should explain why the path can't be greater longer than the greatest longest path from the root to any leaf. For instance, a convincing argument for this step (that doesn't use paths) could be "at each iteration, the algorithm either stops, or recurses down to a child of the current node, which amounts to going down one level of the tree, therefore it must reach a leaf in at most $h$ iterations, at which point it will stop". Try and come up with an argument using paths. It doesn't have to be as rigorous as a formal logic proof, but it should be enough that anyone reading it can convince himself that the argument is solid.

Is the time complexity of the second algorithm also $O(h)$ ? (Thinking)

Maybe. Maybe not. Try running the algorithm on the worst case and best case inputs to the previous algorithm, to see how they compare. Then, look at the code for the second algorithm. What is that while loop doing? Run through both algorithms step by step on the same input. Aren't they basically doing the same thing? What does that mean? Often just walking through each step of the algorithm is the best way to understand it, it's not just for computers!