Bissoy.com
Doctors Medicines MCQs Q&A

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n?

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n? Correct Answer θ(log<sub>2</sub>(n))

The correct answer is option 3:

Key Points

  • Binary search has the Worst-case and avg case time complexity O(log2n) and best case O(1) in an array. So, it is can also be written as θ(log2n)

and θ (1).

  • No of arithmetic operations will be θ (logn) in the worst case as every comparison needs 2 operations + and / by 2.

Related Questions

A teacher asked the class to subtract 5 from 75.70% of the class said: 25. Their work was shown as: \(\begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} 7&5 \end{array}}\\ {\underline {\begin{array}{*{20}{c}}\ { - 5} \ \ \ &{} \end{array}} }\\ {\underline {\begin{array}{*{20}{c}} 2&5 \end{array}} } \end{array}\) Which of the following describes the most appropriate remedial action that the teacher should take to clarify this misconception?
We create a binary search tree B1 by inserting the numbers 1, 2, 3, 4, 5 into an empty binary search tree. We create another binary search tree B2 by inserting the numbers into an empty binary search tree in the reverse order. What is the difference between the right-most element of B1 and the left-most element of B2?
Can linear search recursive algorithm and binary search recursive algorithm be performed on an unordered list?
The usual O(n2) implementation of insertion sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will
A class III mathematics teacher gave the following questions to her students:  \(\begin{equation} \frac{ \begin{array}[b]{r} 256 \\ + 173 \end{array} }{ } \end{equation}\) \(\begin{equation} \frac{ \begin{array}[b]{r} 28 \\ + 32 \end{array} }{ } \end{equation}\) \(\begin{equation} \frac{ \begin{array}[b]{r} 129 \\ + 76 \end{array} }{ } \end{equation}\) Later she asks the students to solve a worksheet that has similar questions. Which of the following statements is appropriate for the given situation?
A material is loaded elastically under plane stress condition given by the following tensor:
\[\left[ {\begin{array}{*{20}{c}} 1 \\ 0 \end{array}\begin{array}{*{20}{c}} 2 \\ 1 \end{array}\begin{array}{*{20}{c}} 0 \\ 0 \end{array}} \right
Consider the following regarding the drawbacks of BCD arithmetic over binary arithmetic : 1. Perform arithmetic operations indirectly on decimal data. 2. Take more time for execution. 3. Less efficient use of memory. 4. Small number of computations are required. Which of the above drawbacks are correct ?  
S1: The mail is first collected from different letter boxes.
P: From there it is sent to the head post office.
Q: It is then sorted out at the sorting office.
R: The mail is again sorted out at the head office by the concerned beat postman.
S: The sorted mail is sent to the zonal post office.
S6: Finally it is delivered to us.

The Proper sequence should be:
Study the given pattern carefully and select the number that can replace the question mark (?) in it. First row: 73, 52, 75 Second row: 64, 41, 63 Third row: 68, 47, ? (NOTE: Operations should be performed on the whole numbers, without breaking down the number into its constituent digits. For example, 13 – Operations on 13 such as adding/deleting/multiplying etc. to 13 can be performed. Breaking down 13 into 1 and 3 and then performing mathematical operations on 1 and 3 is not allowed.)
Given delta is a global array and number of elements in the sorted array is 10, what are the values in the delta array?