What is the worst case time complexity of the binary tree sort?
2024
What is the worst case time complexity of the binary tree sort?
- A.
O(n)
- B.
O(n log n)
- C.
O(n²)
- D.
More than one of the above
- E.
None of the above
Attempted by 713 students.
Show answer & explanation
Correct answer: C
Binary Tree Sort Worst Case Time Complexity
Binary tree sort involves inserting elements into a binary search tree and then performing an in-order traversal. The time complexity depends heavily on the height of the tree.
In the worst-case scenario, the input data is already sorted or reverse sorted. This causes the binary search tree to become completely skewed, effectively turning into a linked list.
When the tree is skewed, the height becomes equal to the number of nodes, n. Inserting each element then takes O(n) time in the worst case, leading to a total insertion time of O(n²).
Thus, the worst-case time complexity is O(n²).
बाइनरी ट्री सॉर्ट की सबसे खराब (Worst Case) समय जटिलता
बाइनरी ट्री सॉर्ट में तत्वों को बाइनरी सर्च ट्री में डाला जाता है और फिर इन-ऑर्डर ट्रावर्सल किया जाता है। समय जटिलता ट्री की ऊंचाई पर निर्भर करती है।
सबसे खराब स्थिति में, इनपुट डेटा पहले से ही क्रमबद्ध या उल्टा क्रमबद्ध होता है। इससे बाइनरी सर्च ट्री पूरी तरह से तिरछा (skewed) हो जाता है, जो एक लिंक्ड लिस्ट जैसा व्यवहार करता है।
जब ट्री तिरछी होती है, तो उसकी ऊंचाई नोड्स की संख्या, n के बराबर हो जाती है। प्रत्येक तत्व को डालने में सबसे खराब स्थिति में O(n) समय लगता है, जिससे कुल डालने का समय O(n²) हो जाता है।
इसलिए, सबसे खराब स्थिति की समय जटिलता O(n²) है।