CODEWITHSUNDEEP
performancedata-structurestime-complexitybinary-search-tree
the_islander
the_islander

Reputation: 217

Time Complexity of BST

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.

Upvotes: 1

Views: 1376

Answers (2)

Rahul Tripathi
Rahul Tripathi

Reputation: 172628

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.

Upvotes: 3

Ashish Singh
Ashish Singh

Reputation: 181

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

Upvotes: 1

Related Questions