Register

UPPCL AE 2018:55

• retagged by
395 views
0 votes
0 votes

An unordered list contains $n$ distinct elements. The number of comparisons to find an element in the list that is larger than the second minimum in the list is

  1. $\Theta(n \log n)$
  2. $\Theta(n/ \log n)$
  3. $\Theta(1)$
  4. $\Theta(\log n)$
• retagged by
User Avatar

1 Answer

1 votes
1 votes
I think just 3 comparisons are needed among 1st, 3 elements of the array. the elements greater in this 1st, 3 elements will definitely be greater than the 2nd minimum element.

Hence T(n)  = O(1)
User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
admin asked Jan 5, 2019
454 views
UPPCL AE 2018:38
Which of the given options provides the increasing order of asymptotic complexity of functions $\text{f}_{1}, \text{f}_{2}, \text{f}_{3}$ and $ \text{f}_{4} $ ... $\text{f}_{4}, \text{f}_{3}, \text{f}_{2}, \text{f}_{1}$
Which of the given options provides the increasing order of asymptotic complexity of functions $\text{f}_{1}, \text{f}_{2}, \text{f}_{3}$ and $ \text{f}_{4} $ ?$\text{f}_...
User Avatar
0 votes
0 votes
1 answer
2
admin asked Jan 5, 2019
302 views
UPPCL AE 2018:23
Consider the following code snippet. It accepts a positive integer $n$ as input. int i = 0, j = 0, val = 1; for(i = 1; i <= n; i++) { j = n; if (i%2 == 0) { while(j>1) { val = val * j; j = j / 2; } } } What is the worst-case time complexity of the algorithm? $O(n)$ $O(n^{2})$ $O(n^{2} \log n)$ $O (n \log n)$
Consider the following code snippet. It accepts a positive integer $n$ as input.int i = 0, j = 0, val = 1; for(i = 1; i <= n; i++) { j = n; if (i%2 == 0) { while(j>1) { v...
User Avatar
0 votes
0 votes
1 answer
3
admin asked Jan 5, 2019
295 views
UPPCL AE 2018:72
The recurrence equation $T(n) = T(\sqrt{n}) + O(1)$ has the following asymptotic solution: $T(n) = O(\sqrt{n})$ $T(n) = O(\log n)$ $T(n) = O(n^{1/\log n})$ $T(n) = O(\log \log n)$
The recurrence equation $T(n) = T(\sqrt{n}) + O(1)$ has the following asymptotic solution:$T(n) = O(\sqrt{n})$$T(n) = O(\log n)$$T(n) = O(n^{1/\log n})$$T(n) = O(\log \lo...
User Avatar
0 votes
0 votes
0 answers
4
admin asked Jan 5, 2019
217 views
UPPCL AE 2018:56
The Adjacency matrix of a directed graph $\text{G}$ ... $(h, c, a, e, f, d, i, g, b)$ $(c, a, d, e, f, g, h, i, b)$
The Adjacency matrix of a directed graph $\text{G}$ is given below.$\begin{array} {} & a & b & c & d & e & f & g & h & i \\ a & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ b & ...
User Avatar
Link Copied!