What is the worst-case number of arithmetic operations performed by recursive…
2025
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?
- A.
θ(n)
- B.
θ(√n)
- C.
θ(log2(n))
- D.
θ(n2)
Attempted by 91 students.
Show answer & explanation
Correct answer: C
In recursive binary search, the algorithm repeatedly divides the sorted array in half. At each step, it performs two arithmetic operations: calculating the midpoint (mid = low + (high - low) / 2) and comparing the target with the middle element.
Since the search space is halved in each recursive call, the number of recursive calls required in the worst case is log₂(n).
Each call involves 2 arithmetic operations (addition and division by 2), so the total number of arithmetic operations is 2 × log₂(n), which is θ(log₂n).
Therefore, the worst-case number of arithmetic operations is θ(log₂n).
हिन्दी उत्तर:
रिकर्सिव बाइनरी सर्च में, एल्गोरिथ्म लगातार सॉर्टेड एरे को आधा भाग में विभाजित करता है। प्रत्येक चरण में, यह मिडपॉइंट की गणना (mid = low + (high - low) / 2) और टार्गेट की तुलना मध्य तत्व के साथ करता है।
चूंकि प्रत्येक रिकर्सिव कॉल में खोज स्पेस आधा हो जाता है, इसलिए खराबतम स्थिति में आवश्यक रिकर्सिव कॉलों की संख्या log₂(n) है।
प्रत्येक कॉल में 2 अंकगणितीय संचालन (जोड़ और 2 से विभाजन) शामिल होते हैं, इसलिए कुल अंकगणितीय संचालनों की संख्या 2 × log₂(n) है, जो θ(log₂n) है।
इसलिए, अंकगणितीय संचालनों की खराबतम संख्या θ(log₂n) है।