Register

How could you find first occurence in Logn time using a variant of BS?

• retagged by
1,089 views
0 votes
0 votes
I mean i guess it should be in O(n/2) i.e. O(n) time. Because one must check for every element starting from the first one till n/2 th element & for each of which one must whether A[i]==A[n/2 +i].

Please explain.
related to an answer for: GATE CSE 2008 | Question: 40
• retagged by
User Avatar

1 Answer

2 votes
2 votes
Let for a particular index i check that condition A[i]==A[i+1] or not..
 if it is true then (check A[2i]==A[n/2+1] or not )
else select i+1 for same purpose..

let size of array is 100 and A[0]=A[2]=A[4]!=A[8]
then dont check for A[2] as well as A[4]..
this ll reduce no of comparison to logn..
• edited by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

506
views
1 answers
0 votes
dhruba asked May 29, 2023
506 views
Consider a divide and conquer algorithm that divides an input of size n into a subproblems, each of size n/b, and the cost of dividing and merging the problems is given by f(n) = Θ(n^c). The Master Theorem classifies this into different cases based on the value of c in relation to log_b(a). Could you explain the intuition and reasoning behind these classifications?
Consider a divide and conquer algorithm that divides an input of size n into a subproblems, each of size n/b, and the cost of dividing and merging the problems is given b...
User Avatar
292
views
0 answers
0 votes
usdid asked Apr 16, 2022
292 views
a) what is the iterative equation showing the running time of the algorithm whose pseudocode is given below? b) What is this repeated equation in asymptotic notation using the Master's theorem. c) What is the same repeated equation in asymptotic notation using the recursion tree method.
a) what is the iterative equation showing the running time of the algorithm whose pseudocode is given below? b) What is this repeated equation in asymptotic notation usin...
User Avatar
1.8k
views
2 answers
2 votes
Vikrant Singh asked Jan 31, 2015
1,784 views
What is the worst case time complexity to find the gcd(m,n) using best algorithm known?
What is the worst case time complexity to find the gcd(m,n) using best algorithm known?A. O(log(min(m,n)))B, O(log(max(m,n)))
User Avatar
437
views
0 answers
0 votes
iarnav asked May 13, 2018
437 views
#Algorithms #DFS How to find if a directed graph G is strongly connected using DFS in one pass?
I know, Kosaraju algorithm and there's one other algorithm which involves reversing of G and using DFS, but two times, but there's some algorithm which uses DFS only time...
User Avatar
Link Copied!