GATE CSE 2021 Set 2 | Question: 8

Question

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

• A. $\Theta ( \sqrt{n})$
• B. $\Theta (\log _2(n))$
• C. $\Theta(n^2)$
• D. $\Theta(n)$

Comments

Option B?

---

(B) logn offcourse

---

Correct option is B .

As avg case and worst case tc for BS is O(log n).

---

Every binary search pass will perform 2 operations. "+" & "/ by 2". so no. of arithmatic operations = 2*logn which is Θ(logn)

Answer 1

Worst-case number of arithmetic operations performed by recursive binary search on a sorted array is given by the following recurrence relation:

$T(n) = T(\frac{n}{2}) + \Theta(1) $

$\text{for }~T(n) = aT(\frac{n}{b}) + f(n), \\ a\geq 1, b > 1$

$\text{Case 2 of master theorem says,}$

$\text{if}~~f(n) = \Theta(n^{\log_ba}) \\ \text{then}~~T(n) = \Theta(n^{\log_ba}\cdot \log(n)) $

$\text{Here, }n^{\log_b(a)} = n^{\log_2(1)} = n^0 = 1\\ \Rightarrow f(n) = \Theta(n^{\log_b(a)}) $

$\text{Hence, we can conclude that }T(n) = \Theta(1\cdot \log_2(n)) = \Theta(\log_2(n))$

B is correct

Comments

@Nikhil_dhama what if O(logn) was also given in option ??

---

@abir_banerjee Then also ϴ( log n ) should be correct as its more tighter bound than O( log n )

---

abir_banerjee

we have to select the exact one then not the upper-bound.

Answer 2

option B 

Binary search which can be recursively applied on sorted data items 

has Worst case and avg case time complexity O(log n) and  best case O(1)  or it is also correct to write as Θ(logn)

and Θ(1) since worst case /avg case /best case are both upper bound and lower bound by  log n / log n / 1

https://en.wikipedia.org/wiki/Binary_search_algorithm

No of arithmetic operations will  be Θ(logn) in worst case  as every comparison need 2 operation + and / by 2

Comments

What are arithmetic operations performed in recursive binary search?

---

They will also be same as every comparison need two operations (addition and division) mid = beg+end/2

---

Computation of mid element requires arithmetic operations:

Lower Mid: [ start + (end-start)/2 ] or Upper mid: [ start + (end – start +1)/2 ]

Answer 3

The operation has to be performed on one element in the sorted binary tree. Thus the recursive function becomes-

T(n)=  T(n/2) + 1   where 1 represents the operation performed. So by masters theorem  Θ(log2(n)). Hence option B

Answer 4

(B.) Binary Search WC T.c. Is- O(log(n))