in DS recategorized by
103 views
1 vote
1 vote

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,

  1. $c=3 n$
  2. $c=2 n+5$
  3. $c \geq 3 n-1$
  4. $c \leq n$
  5. $c \leq 2 n+3 $
in DS recategorized by
by
103 views

1 Answer

2 votes
2 votes

We need atmost 2n+3 comparisons 

we will see why

Answer:

Related questions