1

so I know that operation on a BST operate in log time because of the halving of the structure, I was wondering what the time complexity would be if you search for a value that was not in the structure.

2 Answers 2

3

The average case time complexity will be O(log n) and the worst case would be O(n). To understand the O(log n) complexity you can refer What does O(log n) mean exactly?

This image will explain you how part:

enter image description here

I will also recommend to go through the wiki for details.

1

It will still be O(log n). Think this way, it will search by continuously halving till it cannot locate.

2
  • Thanks for the reply, but how would it know whether the value is greater or less than the root to know what side to start looking in? I was under the impression that it would do one side then do the next and realize it isn't there May 8, 2015 at 5:35
  • You're talking about a BST. A BST would be arranged in the following manner leftChild < root < rightChild Now, if you think about it your element would be first comparing itself with the root of the tree and then decide whether to go with the leftChild or the rightChild May 8, 2015 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.