edited by
5,075 views
31 votes
31 votes

Let $A$ be an $n \times n$ matrix such that the elements in each row and each column are arranged in ascending order. Draw a decision tree, which finds $1$st, $2$nd and $3$rd smallest elements in minimum number of comparisons.

edited by

3 Answers

Best answer
35 votes
35 votes

This is a two dimensional array of size $4\times4$.
$2$____$5$____$8$____$9$
$4$____$11$___$19$___$21$
$6$____$13$___$24$___$27$
$8$____$15$___$25$___$29$

You can see the elements in each row and each column are arranged in ascending order. 
Smallest element: $A[0][0]   = 2$
$2^{nd}$ smallest element: $\min(A[0][1],A[1][0])= \min(5,4)=4$
$3^{rd}$ smallest element: Just exclude the element you got as $2$$^{nd}$ smallest$(4)$. Here, we can compare $A[2][0],A[0][1]$ no need to compare with $A[0][2]$. So, it depends upon from where you got $2^{nd}$ element. You can draw a decision tree. If you got $2^{nd}$ best from $A[0][1]$ then what to do & if you get from $A[1][0]$ then what to do.

Any way, time complexity is simply O(1).
The elements are in ascending order. Not in non decreasing order. Clearly they are all distinct in a particular row or column.

edited by
10 votes
10 votes

If all elements are distinct we have to check 1st row and 1st column.So complexity will be O(n2)

Here minimum no of comparison could be 1 , because a[0][0] will be minimum always, now we have to check between a[0][1] and a[1][0]

if all elements are not distinct we have to search all elements of the array

So, minimum comparison could be O(1)

3 votes
3 votes

The smallest element is A[0][0] 

The second smallest element is min(A[0][1], A[1],[0])

The decision tree for finding the third smallest element is as follows -

 

Related questions

26 votes
26 votes
2 answers
1
Kathleen asked Sep 23, 2014
9,222 views
A sorting technique is called stable ifit takes $O (n \log n)$ timeit maintains the relative order of occurrence of non-distinct elementsit uses divide and conquer paradi...
41 votes
41 votes
3 answers
2