Home › Previous year questions › GATE 2008 CS › Question 40GATE 2008 CS – Question 40 Algorithms · Searching, Sorting and Hashing · 2 marks · Multiple choice
What minimum asymptotic number of comparisons determines whether an integer appears more than n/2 times in a sorted n-integer array?
$\Theta(n)$ $\Theta(\log n)$ $\Theta(\log^*n)$ $\Theta(1)$ Practise this question in The GATE Grind →
Show answer and explanation Correct answer: (B) $\Theta(\log n)$
Explanation We are sorry we couldn't write detailed soluition for this, we are working on it!, please consider asking your own AI, its just 2-3 clicks with very minimum effort
More Searching, Sorting and Hashing questions GATE 2007 CS Q14 – Which sort has lowest worst-case complexity? GATE 2007 CS Q40 – An empty size7 hash table starts at index0, h(x)=(3x+4) mod7. Insert1, 3, 8, 10 with… GATE 2007 CS Q50 – An array has an even number n of elements. To find both its minimum and maximum, which… GATE 2026 CS (CS1) Q24 – Consider a hash table P[0, 1, , 10] that is initially empty. The hash table is maintained… GATE 2026 CS (CS2) Q30 – The keys 5, 28, 19, 15, 26, 33, 12, 17, and 10 are inserted into a hash table using the… GATE 2025 CS (CS1) Q33 – The pseudocode of a function fun() is given below: Let A[0,...,29] be an array storing 30… All Searching, Sorting and Hashing questions →