Register

How can we found second smallest element with n+[lgn]-2 comparisons in worst case ??

• retagged by
3,517 views

1 Answer

2 votes
2 votes
divide and conquer approach gives min element with n-1 comparison..
for 2nd minimum element search on d root to leaf path from where max element  coming.. reason is second minimum element must compared with minimal element when we were  finding minimum element.. so ,

divide and conquer based on binary tree approach so no of elements from root to leaf path from where MIN element is coming is logn .. finding min from logn elements takes logn -1 comparison..
total n-1+logn-1 = n + logn -2 comparison
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
2 answers
1
dhruba asked Jun 5, 2023
1,161 views
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). How many comparisons are needed in the worst case scenario to determine that the key is not in the array?
Binary search is performed on a sorted array of n elements. The search key is not in the array and falls between the elements at positions m and m+1 (where 1 ≤ m < n). ...
User Avatar
4 votes
4 votes
2 answers
3
worst_engineer asked Oct 7, 2015
6,083 views
In quick sort , for sorting n elements , the (n/4)th smallest element
In quick sort , for sorting n elements , the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What will be the time complexity? it is $\Theta (n^{2})$ , right ?
In quick sort , for sorting n elements , the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What will be the time complexity?it is $\Theta (...
User Avatar
1 votes
1 votes
1 answer
4
Meenakshi Sharma asked Nov 13, 2016
773 views
no of comparisons are needed in the worst case to find min and max in an array
User Avatar
Link Copied!