Register

IITd Phd -sample Q

• retagged by
906 views

1 Answer

3 votes
3 votes

I think time complexity for both "actual binary search and modified binary search will b asymptotically same "
   consider recurrence relation for worst case of modified b.s.
   T(n)=  c    if n=1
           =T(2n/3) +c if n>1
  after solving r.r. ans= log3/2n   

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
Aboveallplayer asked Dec 1, 2016
685 views
IITD phd-sample Q
You are given a heap containing N elements. Write a procedure which takes as input a parameter k, and outputs the k'th smallest number in the heap. The running time of the procedure must depend on k alone.
You are given a heap containing N elements. Write a procedure which takes as input a parameter k, and outputs the k'th smallest number in the heap. The running time of th...
User Avatar
14 votes
14 votes
4 answers
2
Arjun asked Feb 18, 2021
12,135 views
GATE CSE 2021 Set 2 | Question: 8
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$? $\Theta ( \sqrt{n})$ $\Theta (\log _2(n))$ $\Theta(n^2)$ $\Theta(n)$
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$?$\Theta ( \sqrt{n})$$\Theta (\log _2(n))$$\Theta...
User Avatar
0 votes
0 votes
1 answer
3
Sabir Khan asked Aug 8, 2018
1,110 views
Binary search
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is (A) (n) (B) (logn) (C) (log*n) (D) (1)
The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is(A) (n)(B) (logn)(C) (log*n)(D) (1)
User Avatar
Link Copied!