# Selection Problem - Matrix

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 05-01-2009
anirban
Selection Problem - Matrix
Let A be a real valued matrix of order n*n already stored in memory. Its (i, j)-th element is denoted by a[i, j]. The elements of the matrix A satisfy the following property:

Let the largest element in row i occur in column Li. Now, for any two rows i1, i2, if i1<i2, then Li1<=Li2.

(a)
2 6 4 5 3
5 3 7 2 4
4 2 10 7 8
6 4 5 9 7
3 7 6 8 12

(b)

Row I l(i)
1 2
2 3
3 3
4 4
5 5

Figure shows an example of (a) matrix A, and (b) the corresponding values of l_i for each row i.

Write an algorithm for identifying the largest valued element in matrix A which performs at most O(n*logn) comparisons.
• 05-02-2009
stevesmithx
To get better help, post the code you have so far.
• 05-02-2009
anirban
no i just want the algo in O(nlogn) time please
• 05-03-2009
OnionKnight
Quote:

Originally Posted by anirban
for any two rows i1, i2, if i1<i2

What does it mean that a row is less than another?
• 05-03-2009
anirban
means row number i1 < row number i2
• 05-03-2009
stevesmithx
Quote:

Write an algorithm for identifying the largest valued element in matrix A which performs at most O(n*logn) comparisons.
Are you certain that it is O(n*log n)?
Because i think that would mean you can perform only 4(~3.5) comparisons at most
for the example problem you have posted.
• 05-03-2009
laserlight
Quote:

Originally Posted by anirban
means row number i1 < row number i2

Honestly, I do not understand what that means either. What is a row number?
• 05-03-2009
stevesmithx
I think the OP is referring to the index number of the rows of the matrix (a)
Quote:

(a)
1->2 6 4 5 3
2->5 3 7 2 4
3->4 2 10 7 8
4->6 4 5 9 7
5->3 7 6 8 12
The second matrix (b) have the indices of these rows in their 1st column
and the indices of the columns having the largest number in the current row in the 2nd column.
This problem would be much easier to solve without the O(nlogn) restriction. ;) :p
• 05-05-2009
OnionKnight
Quote:

Originally Posted by stevesmithx
I think the OP is referring to the index number of the rows of the matrix (a)

The second matrix (b) have the indices of these rows in their 1st column
and the indices of the columns having the largest number in the current row in the 2nd column.
This problem would be much easier to solve without the O(nlogn) restriction. ;) :p

The ordo notation gives upper bounds, which means the obvious O(n) solution is also O(n*log(n)). Not sure if I want to point it out though, seems to be an awful lot like "do my homework".
• 05-05-2009
brewbuck
Quote:

Originally Posted by anirban
no i just want the algo in O(nlogn) time please

You aren't going to get it.
• 05-06-2009
arpsmack
Quote:

Originally Posted by stevesmithx
Are you certain that it is O(n*log n)?
Because i think that would mean you can perform only 4(~3.5) comparisons at most
for the example problem you have posted.

This is not true, you are ignoring the hidden constant. In fact, the algorithm could use 1 billion comparisons for a 5x5 matrix and still be O(n log n).

On a less important note, logarithms in computer science typically refer to the log base 2, while you are calculating the log base 10. This doesn't matter quite as much since logs of different bases are proportional to each other by a constant factor, making them equivalent in Big-Oh notation.
Quote:

Originally Posted by OnionKnight
which means the obvious O(n) solution

I would be interested in hearing your O(n) solution because I'm pretty sure no O(n) solution exists. I'm thinking that you are probably misunderstanding the problem, but I'm willing to hear you out.

@anirban:

The presence of "log n" in the upper bound for an algorithm usually indicates some kind of divide-and-conquer approach. Consider an algorithm like mergesort: divide the list in half, sort each half, merge the two halves.

Is there a way you can partition your problem into two smaller chunks, and then recursively perform your algorithm on those chunks? This hopefully starts you off in the right direction. If not, then there isn't much I can say besides just handing you an answer.
• 05-06-2009
stevesmithx
Quote:

Originally Posted by arpsmack
On a less important note, logarithms in computer science typically refer to the log base 2, while you are calculating the log base 10. This doesn't matter quite as much since logs of different bases are proportional to each other by a constant factor, making them equivalent in Big-Oh notation.

I agree with this. Now the n log n evaluates to 12 for n=5.

Quote:

Originally Posted by arpsmack
This is not true, you are ignoring the hidden constant. In fact, the algorithm could use 1 billion comparisons for a 5x5 matrix and still be O(n log n).

Hmm, I am confused here.
Could you explain what hidden constant i am missing here?
i think you are exaggerating when you say 1 billion!! here :D
• 05-06-2009
brewbuck
Quote:

Originally Posted by stevesmithx
I agree with this. Now the n log n evaluates to 12 for n=5.

Hmm, I am confused here.
Could you explain what hidden constant i am missing here?
i think you are exaggerating when you say 1 billion!! here :D

Big-Oh notation talks about limits and "aymptotic behavior." I.e. the SHAPE of the curve as N increases. It says nothing about the overall SLOPE of the curve.
• 05-06-2009
arpsmack
Quote:

Originally Posted by stevesmithx
Hmm, I am confused here.
Could you explain what hidden constant i am missing here?
i think you are exaggerating when you say 1 billion!! here :D

Actually, I'm not exaggerating at all.

Lets say the function f(n) returns the number of steps required to complete your algorithm for a given value of n.

In order for f to be O(n):

There must be certain value of n (lets call it N) when f(n) <= K*n for all values of n > N. K is any constant at all. It could be 1, or it could be 1 billion.

... I'm sorry, I'm just going to stop. I'm butchering this explanation. It would really make a lot more sense if we were chatting in person and I could draw a picture or something :)

I just thought of a great example that might help.

Think of it this way: Big-O notation doesn't describe how fast your algorithm is. It loosely describes how much it grows as you increase the problem size.

If your algorithm did 1 billion comparisons for a 5x5 matrix, or a 10x10 matrix, or any sized matrix, then it would be O(1). No matter what the problem size is, it always requires 1 billion comparisons.
[/edit]
• 05-07-2009
stevesmithx
Quote:

If your algorithm did 1 billion comparisons for a 5x5 matrix, or a 10x10 matrix, or any sized matrix, then it would be O(1). No matter what the problem size is, it always requires 1 billion comparisons.
That clears my misunderstanding.
Thanks to both of you.
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last