TIFR CSE 2022 | Part B | Question: 5

Question

There is an unsorted list of $n$ integers. You are given $3$ distinct integers and you have to check if all $3$ integers are present in the list or not. The only operation that you are allowed to perform is a comparison. Let $A$ be an algorithm for this task that performs the least number of comparisons. Let $c$ be the number of comparisons done by $A$. Then,

• A. $c=3 n$
• B. $c=2 n+5$
• C. $c \geq 3 n-1$
• D. $c \leq n$
• E. $c \leq 2 n+3 $

Answer 1

We need atmost 2n+3 comparisons 

we will see why