Question:
What is the time complexity to search for an element in a balanced B-Tree with \(n\) keys and order \(m\)?
\(n\) कुंजियों और \(m\) क्रम वाले संतुलित B-ट्री में किसी तत्व को खोजने की समय जटिलता क्या है?
Options:
- \(O(\log n)\)
- \(O(n)\)
- \(O(m \log n)\)
- \(O(n \log m)\)
- \(O(\log n)\)
- \(O(n)\)
- \(O(m \log n)\)
- \(O(n \log m)\)
Correct Answer: a)
Explanation:
The height of a B-Tree of order \(m\) with \(n\) keys is \(O(\log_m n)\). Within each node, searching among \(m\) keys using binary search takes \(O(\log m)\). Total search time is \(O(\log_m n \times \log m) = O(\log n)\).
B-ट्री की ऊंचाई \(O(\log_m n)\) होती है और नोड के अंदर बाइनरी सर्च में \(O(\log m)\) लगता है। कुल खोज समय \(O(\log n)\) होता है।