matrix algorithm

hi,
im a second year communication engineering student and taking a algorithms and data structures course.
we got a question no have been able to solve:

Let M be a matrix with m rows and n columns(m n) with the following
property:if the minimal value in row i is located at M(ij),then the
minimal value in row i+1 is located at M(i+1k),where k j.Design
an algorithm with running time O(n) that finds minimal value for every
row in M.

weve been working on it for more than a week now with no answer. the we came up with is O(nlogn).
any idea,help,moral support aprriciated.

thanx :)

> M(i+1k),where k j.
What did you mean to write there? M(i+1+k) or something else? What does 'where k j' signify?

hi

sorry, just saw paste didnt work as well as i thought...

if the minimal value in row i is located at M(i,j) then the
minimal value in row i+1 is located at M(i+1,k) where k< j.

thanks, again :)

I think u just need to sequential search because you need to determine minimum value for every value. I think there are no others option because the row cannot be sort. Therefore, binary search algorithm is eliminated.

but that wont run in O(n), or am i mistaken.

take a look ..
you want complexity of O(n) , where n is the number of columns. so if u see finding a minimal number is never more than number of column.
Am i right?

Ok, according to your rules:

Quote:

---

if the minimal value in row i is located at M(i,j) then the
minimal value in row i+1 is located at M(i+1,k) where k< j

---

If, for example, m = n, then the minimum values would be the diagonal from the upper right to the bottom left (i.e. (1,n) to (m,1)) since k < j for the next minimum value where j is the column for the current value.

Under these assumptions the minimum value MUST be in a semi diagonal order. As you go down the rows, the next minum value HAS to be to the left of the previous minimum value. Therefore, if you start your search at row = 1, and column = n then you can work your way backwards finding the minimums.

Each time you find a minimum you change your starting point for the column search, since you know the next one has to be k < j. This will make the algorithm O(n) + n-m (but the n-m is a constant factor and is negligable).

To print out an answer, you need m numbers, and m is not constrained by n, so it won't be O(n) if m is much more than n. It's O(m+n). Your please-do-my-homework speech needs some work, it's unrealistic that you worked a week on the problem where you only need to understand the question to write out a solution.

Actually when considering the run time we say that it is O(n) meaning that it is a linear function. When I was saying that it is O(n) + a constant factor I was stating that it will be a linear function + a constant factor of finding the next element for the rows, which is at most n - m (if n > m).

Quote:

---

Originally Posted by ProgramThis

Actually when considering the run time we say that it is O(n) meaning that it is a linear function. When I was saying that it is O(n) + a constant factor I was stating that it will be a linear function + a constant factor of finding the next element for the rows, which is at most n - m (if n > m).

---

A linear function of what? Of current year?

Linear function: as in a function that is only raised to the first power.

I.E. f(x) = x + 4 is a linear function because x is raised to the first power and is noted as O(n) not O(n + 4). As oposed to a quadratic function f(x) = x^2 which would be noted as O(n^2).

*Edit:
I see what you are saying about "what elements" but when talking in general about the run time we don't usually care. If you want to list the EXACT run time that is a different matter. However, when talking about amortized run time (i.e. big O notation of O(n)) most people are generally only concerned with the order of function.

Quote:

---

Originally Posted by RoboTact

To print out an answer, you need m numbers, and m is not constrained by n, so it won't be O(n) if m is much more than n. It's O(m+n). Your please-do-my-homework speech needs some work, it's unrealistic that you worked a week on the problem where you only need to understand the question to write out a solution.

---

Neither of you noticed that if n<m that kind of matrix cannot exist ;-)

Quote:

---

Originally Posted by ProgramThis

As oposed to a quadratic function f(x) = x^2 which would be noted as O(n^2).
.

---

Actually Quadratic is a*x^2 + b*x +c where (a != 0)

Ironically this can cause confusion when dealing with "Big-O".

Consider the ramifications of:

a = 1.0e-10;
b = 1;
c = 1.0e+10;

What is the "correct" Big-O, and what if the "real" Big-O (if x is bounded by some reasonable (<2^32) limit???? :eek:

I gettcha, however according to the proffesors I had, and wikipedia, in Big O notation a quadratic is the term used for O(n^2) run time. In mathematics yes a quadratic is ax^2 + bx + c = 0, but when talking about algorithm analysis the term quadratic refers to O(n^2).

Quote:

---

Originally Posted by TheCPUWizard

Actually Quadratic is a*x^2 + b*x +c where (a != 0)

Ironically this can cause confusion when dealing with "Big-O".

Consider the ramifications of:

a = 1.0e-10;
b = 1;
c = 1.0e+10;

What is the "correct" Big-O, and what if the "real" Big-O (if x is bounded by some reasonable (<2^32) limit???? :eek:

---

What happens when a=1 and b=c=0?
4x^2 - x + 6 is not "more quadratic" than x^2.
A quadratic is just a polynomial of degree 2.

Regarding your example, asymptotic estimations are valid only for x->inf, therefore O(ax^2+bx+c) = O(x^2), regardless of the values of a,b and c.
After all, lim_{x->inf} (ax^2+bx+c)/x^2 = a, then the two polynomials grow with the same speed. For instance, we always write O(log n) regardless of the base of the logarithm because log_a n = log_b n / log_b a, and log_b a is just a constant.

The above comments are all 100% correct.

MY point simply is that too many people thing that

O(1) <= O(n) <= O(nLogn) < O(n^2) < O(n^3)

This in fact has NO actual basis in fact. I have seen many O(n^2) that are so much simpler than an O(nLogn) that for all reasonable values of n, the higher order of complexity is much faster.

Yet people persist in making comments about "efficiency" in terms of "big-O".

Quote:

---

Originally Posted by kiuhnm

Neither of you noticed that if n<m that kind of matrix cannot exist ;-)

---

Right...

Quote:

---

Originally Posted by TheCPUWizard

The above comments are all 100% correct.

MY point simply is that too many people thing that

O(1) <= O(n) <= O(nLogn) < O(n^2) < O(n^3)

This in fact has NO actual basis in fact. I have seen many O(n^2) that are so much simpler than an O(nLogn) that for all reasonable values of n, the higher order of complexity is much faster.

Yet people persist in making comments about "efficiency" in terms of "big-O".

---

Agreed.
But note that "O(1) <= O(n)" is true by definition (if n->inf). You can't say it's false.
To be consistent, you should get rid of the big-O notation and use something else.

Quote:

---

Originally Posted by kiuhnm

Agreed.
But note that "O(1) <= O(n)" is true by definition (if n->inf). You can't say it's false.
To be consistent, you should get rid of the big-O notation and use something else.

---

1) Duh... :blush: :o Smacking Self... :mad: :mad: :thumbd: Of course with the "=" sign there it is tru, and even just as a "<" it would be true in all but the parasitic cases.

2) Internally (here at my firm) we have minimized the use of big O, and created our own concept of big P [deliberately opening up lots of puns]. In this case we actually use a polynomail with rough estimates [typically one of a set of predefined values] for the constant multipliers for each term. While this is not as simple as the conventional approaqch, simple ignorng the multipliers reduces the "equation" to a big-O expression.

This allows us to model different solutions based on additional factors.

And nobody is disputing that constant factors can make a huge difference when considering an algorithm, depending of course on the size of the data set. However, when discussing algorithms in general and talking about their asymptotic behavior nobody gives a crap about the 'a'.


In real world practice: yes you need to consider the size of the data set and the actual run time. Nobody was saying that the 'a' didn't matter in the real world.

You are getting all worked up about this. Did you have a hard time in your algorithms class at school? Did you hate the fact that most of it was theorhetical?

Personally it pissed me off at first. I would tell the teacher 'why the f*ck don't we care about the constant factor, it matters!!!'. And I was right, we just didn't cover that aspect of algorithm analysis until the second semester :)