Register

TIFR CSE 2022 | Part B | Question: 5

• recategorized by
607 views
2 votes
2 votes

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 $
• recategorized by
User Avatar

1 Answer

Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

3 votes
3 votes
1 answer
1
admin asked Sep 1, 2022
546 views
TIFR CSE 2022 | Part B | Question: 1
Which data structure is commonly used to implement breadth first search in a graph? A queue A stack A heap A hash table A splay tree
Which data structure is commonly used to implement breadth first search in a graph?A queueA stackA heapA hash tableA splay tree
User Avatar
4 votes
4 votes
2 answers
3
admin asked Sep 1, 2022
964 views
TIFR CSE 2022 | Part B | Question: 2
Let $G=(V, E)$ be an undirected simple graph. A subset $M \subseteq E$ is a matching in $G$ if distinct edges in $M$ do not share a vertex. A matching is maximal if no strict superset of $M$ is a matching. How many maximal matchings does the following graph have? $1$ $2$ $3$ $4$ $5$
Let $G=(V, E)$ be an undirected simple graph. A subset $M \subseteq E$ is a matching in $G$ if distinct edges in $M$ do not share a vertex. A matching is maximal if no st...
User Avatar
1 votes
1 votes
1 answer
4
admin asked Sep 1, 2022
838 views
TIFR CSE 2022 | Part B | Question: 3
Consider the problem of sorting $n$ single digit integers (base $10$). This problem can be solved in time $O(n \log n)$ but not $O(n \log \log n)$ $O(n \log \log n)$ but not $O(n)$ $O(n)$ but not $O(n / \log \log n)$ $O(n / \log \log n)$ None of the above.
Consider the problem of sorting $n$ single digit integers (base $10$). This problem can be solved in time$O(n \log n)$ but not $O(n \log \log n)$$O(n \log \log n)$ but no...
User Avatar
Link Copied!