Log In
2 votes

GATE CSE 2021 Set 1 | Question-2.8

  1. GATE CSE 2021 Set 1 | Question-10
  2. GATE CSE 2021 Set 1 | Question-10
  3. GATE CSE 2021 Set 1 | Question-10
  4. GATE CSE 2021 Set 1 | Question-10

Let $P$ be an array containing $n$ integers. Let $t$ be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of $n$ elements. Which one of the following choices is correct?

  1. $t>2n-2$
  2. $t>3\lceil \frac{n}{2}\rceil \text{ and } t\leq 2n-2$
  3. $t>n \text{ and } t\leq 3\lceil \frac{n}{2}\rceil$
  4. $t>\lceil \log_2(n)\rceil \text{ and } t\leq n$
in DS
recategorized by

4 Answers

5 votes

The Answer is B. It will take 3n/2 comparisons by divide and conquer, and it will take 2n-2 without D&C.

2 votes

For Normal min max problem it will take

2n-2 Worst case

n-1 Best case


For Divide and conquer we can use tournament tactic and get the answer in 3n/2 comparisions

As the lowest upper bound is asked the answer will be 

C t>n and t<=3|n/2|

I think here no. of comparisons need to be considered rather than bounds. So, as you said “2n-2 Worst case”

So answer should be t>n and t<=2n-2 in my opinion.

Please correct me if wrong!
I might be wrong but according to ME key it is t>3n/2 and T<2n-2
@Arjun please check
1 vote
I believe the answer will be B

lowest upper bound has been asked we need n-1 comparisons in the best case but 2n-2 comparisons in the worst case

similarly if we use divide and conquer method we will get 3(n/2)-2 comparisons in all the cases

as the method is not specified so we have to consider both the worst case comparisons

so it will be between 3(n/2) and 2n-2...i am quite sure for this one correct me if i am wrong
0 votes

Tournament Method:

  • Imagine using merge-sort and you’d divided the array elements in pairs of two, every element is compared with each other.
  • The largest(or smallest if preferred) is selected out of the two and the winners are copied to a new array and the procedure it repeated till we have one element remaining.

For this,
At first we need $\frac{n}{2}$ comparisons(since $\frac{n}{2}$ pairs), then $\frac{n}{4}$, so on this sums to $n$ using AP.

  • For find ingthe smallest elements we would’ve losers left out in the first round $\frac{n}{2}$ losers to be precise.
  • We again use this procedure instead for finding smaller amongst all.

For this,
At first we need $\frac{n}{4}$(since we are pitting losers against losers) comparisons, then $\frac{n}{8}$ so on which sum to $\frac{n}{2}$.


So, we know that the upper bound is $\frac{3n}{2}$(adding up) and will be equal to it. Hence C is the answer.

Another more intuitive way to understand this is the build heap operation.


edited by

Related questions

1 vote
1 answer
Consider the following statements. $S_1$: The sequence of procedure calls corresponds to a preorder traversal of the activation tree. $S_2$: The sequence of procedure returns corresponds to a postorder traversal of the activation tree. Which one of the following options is correct? $S_1$ is true and ... $S_2$ is true $S_1$ is true and $S_2$ is true $S_1$ is false and $S_2$ is false
asked Feb 18 in DS Arjun 238 views
2 votes
3 answers
A binary search tree $T$ contains $n$ distinct elements. What is the time complexity of picking an element in $T$ that is smaller than the maximum element in $T$? $\Theta(n\log n)$ $\Theta(n)$ $\Theta(\log n)$ $\Theta (1)$
asked Feb 18 in DS Arjun 349 views
0 votes
2 answers
Consider the following sequence of operations on an empty stack. $\textsf{push}(54);\textsf{push}(52);\textsf{pop}();\textsf{push}(55);\textsf{push}(62);\textsf{s}=\textsf{pop}();$ ... $\textsf{s+q}$ is ___________.
asked Feb 18 in DS Arjun 270 views
4 votes
2 answers
An $articulation$ $point$ in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let $T$ be a $\text{DFS}$ tree obtained by doing $\text{DFS}$ in a connected undirected graph $G$. Which of the following ... and $y$ is a descendent of $u$ in $T$, then all paths from $x$ to $y$ in $G$ must pass through $u$.
asked Feb 18 in DS Arjun 1.6k views