GATE 2015 CS (CS2) – Question 16

Algorithms · Asymptotic Analysis and Time/Space Complexity · 1 mark · Multiple choice

An unordered list contains n distinct elements. How many comparisons are needed to find any element that is neither its maximum nor minimum? Assume n≥3.

$\Theta(n\log n)$
$\Theta(n)$
$\Theta(\log n)$
$\Theta(1)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $\Theta(1)$

Explanation

Inspect any three elements and return their median, found using at most three comparisons. At least one selected element is smaller and another larger, so this median cannot be a global extreme. The work is independent of n, hence Θ(1), D.

More Asymptotic Analysis and Time/Space Complexity questions

GATE 2015 CS (CS2) Q26 – Decision problem Q1 reduces in polynomial time to 3-SAT, and 3-SAT reduces in polynomial…
GATE 2015 CS (CS3) Q20 – For i=0n i3=X, consider I (n4), II (n5), III O(n5), IV (n3). Which may replace X?
GATE 2015 CS (CS3) Q37 – Worst-case mergesort takes 30 seconds for input size 64. Which best approximates the…
GATE 2015 CS (CS3) Q41 – L1≤pL2, L3≤pL2 and L2≤pL4. Which are guaranteed? I: L4∈P implies L2∈P. II: L1∈P or L3∈P…
GATE 2015 CS (CS3) Q64 – For positive integer n, f(n)=n and g(n)=n1+ n. Which hold? I: f=O(g). II: f=Ω(g).
GATE 2021 CS (CS2) Q49 – For constants a≥1,b>1, T(n)=aT(n/b)+f(n). Which general claim is correct, under the usual…

All Asymptotic Analysis and Time/Space Complexity questions →