Discussion
What is the time complexity of searching for an element in a balanced Binary Search Tree with n nodes ?
Answer: B
Searching a balanced BST takes O(log n) time.
Each comparison moves the search one level down the tree, so the cost is the height of the tree. A balanced tree (AVL, red-black and so on) keeps its height proportional to log n, so a search makes at most about log n comparisons.
O(n) is the worst case of an unbalanced BST that has degenerated into a chain. O(n log n) is the cost of building or sorting, not of one search. O(1) is the average for hashing, not for a search tree.
No comment is present. Be the first to comment.
Loading…
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development