CODEWITHSUNDEEP
big-obinary-search-tree
rohitt
rohitt

Reputation: 1215

worst case time complexity of BST

I've seen many times that the time complexity of search in BST is O(log(N)) where N is the number of nodes. But shouldn't it be O(N)?

Is it correct to use the worst-case instead of the average-case?

Upvotes: 0

Views: 389

Answers (1)

Papai from BEKOAIL
Papai from BEKOAIL

Reputation: 1529

The common operation we can perform over BST is:

  1. Insert a Node
  2. Search a Node
  3. Delete a Node

The time complexity of all operation falls in O(H); where H - is the height of the tree.

Now, coming to your question, yes IT IS right / correct to use the term worst - case instead of average (or best) case when you define a BST.

Notes: When your BST is skewed, in that case particularly, you can't divide your BST into halves (left and right), so many of us don't consider this as BST rather define it as unordered list with no benefit of BST.

Upvotes: 1

Related Questions