The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+16 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.

A beautiful question on the same concept, https://gateoverflow.in/2766/gate1996_14

+14 votes

Best answer

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.

@ahwan

yes, it is fine,

just one doubt , what you want to say by this statement " The elements are in **ascending order**. *Not in non decreasing order*. " here non decreasing means also increasing order right ?

Numbers are said to be in **ascending order** when they are arranged from the smallest to the largest number so that is increasing order, same meaning is not it ?

increasing: 1 2 3 4

non decreasing: 1 1 2 3

So by ascending order they mean strictly increasing. Otherwise we have to check more elements. Sometimes we may have to check every element.

https://stackoverflow.com/questions/1963474/is-a-non-decreasing-sequence-increasing

"The elements are in ascending order (not in non decreasing order) This line clearly say, they are all distinct in a particular row or column."

+7 votes

If all elements are distinct we have to check 1st row and 1st column.So complexity will be O(n^{2})

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)

@srestha can we do like this??

A[0][0] is smallest so delete it and rearrange matrix which takes not more than n comparisions.

after rearranging at A[0][0] next element can be found.

like this way total number of comparisions=3(n)=O(n)

A[0][0] is smallest so delete it and rearrange matrix which takes not more than n comparisions.

after rearranging at A[0][0] next element can be found.

like this way total number of comparisions=3(n)=O(n)

(0,0) will be smallest.

First comparison will be in (1,0) and (0,1) indices.

second comparison between (0,2) (1,1) (2,0) indices

First comparison will be in (1,0) and (0,1) indices.

second comparison between (0,2) (1,1) (2,0) indices

@srestha dont we need to do any other comparison except between a[0][1] and a[1][0]?

i mean between a[2][0] and a[0][2]there wont be any comparison?if no,pls tell me why..?

i mean between a[2][0] and a[0][2]there wont be any comparison?if no,pls tell me why..?

I think it could also be done with young tableau,rt?

https://gateoverflow.in/8148/gate2015-2_31

but also told it should be done in min no. of comparison

Why u write O($n^2$) ?

We can always find consecutive 3 smallest in O(1) time right ?

a[0][0], a[0][1] and a[1][0] these are 3 smallest in some order. All other elements are either greater or equal to them.

Is it correct ?

We can always find consecutive 3 smallest in O(1) time right ?

a[0][0], a[0][1] and a[1][0] these are 3 smallest in some order. All other elements are either greater or equal to them.

Is it correct ?

yes complexity could be less.

But how do u say 3 smallest could be inside a[0][0] , a[0][1] and a[1][0]?

It also could be in between a[0][0], a[0][1], a[0][2] , rt?

But how do u say 3 smallest could be inside a[0][0] , a[0][1] and a[1][0]?

It also could be in between a[0][0], a[0][1], a[0][2] , rt?

@srestha mam

a[0][0] will be first minimum, no doubt in that

But, the 2nd minimum can be found by comparing a[0][1] and a[1][0].

Lets suppose a[0][1] is 2nd minimum then 3rd minimum can be found by comparing a[0][2] and a[1] [0].

And if a[1][0] is 2nd minimum then 3rd minimum can be found by comparing a[2][0] and a[0] [1].

Total Comparisons=2

Each time we are doing only a constant number of comparisons and hence O(1) time complexity.

Can you point out where I am mistaking.

a[0][0] will be first minimum, no doubt in that

But, the 2nd minimum can be found by comparing a[0][1] and a[1][0].

Lets suppose a[0][1] is 2nd minimum then 3rd minimum can be found by comparing a[0][2] and a[1] [0].

And if a[1][0] is 2nd minimum then 3rd minimum can be found by comparing a[2][0] and a[0] [1].

Total Comparisons=2

Each time we are doing only a constant number of comparisons and hence O(1) time complexity.

Can you point out where I am mistaking.

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.7k
- Digital Logic 1.9k
- Programming & DS 3.5k
- Algorithms 3k
- Theory of Computation 3.7k
- Compiler Design 1.5k
- Databases 2.8k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 835
- Others 1.2k
- Admissions 263
- Exam Queries 390
- Tier 1 Placement Questions 17
- Job Queries 50
- Projects 6

33,593 questions

40,128 answers

114,021 comments

38,389 users