Time Complexity of BST

Question

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.

score 3 · Accepted Answer · edited May 23 '17 at 12:14

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.

edited May 23 '17 at 12:14

Community

1
1

answered May 08 '15 at 05:34

Rahul Tripathi

168,305
31
280
331

Ashish Singh · Answer 2 · 2015-05-08T05:35:10.877

1

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

edited May 08 '15 at 05:35

answered May 08 '15 at 05:29

Ashish Singh

181
1
4

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 – the_islander May 08 '15 at 05: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 – Kaushik Thirthappa May 08 '15 at 09:42

Time Complexity of BST

2 Answers2