matrix algorithm

[goofymickey]

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

[pm_kirkham]

> 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?

[goofymickey]

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

[Peter_APIIT]

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.

[goofymickey]

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

[honey_pisces]

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?

[ProgramThis]

Ok, according to your rules:

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).

[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.

[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).

[RoboTact]

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?

[ProgramThis]

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.

[kiuhnm]

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 ;-)

[TheCPUWizard]

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????

[ProgramThis]

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).

[kiuhnm]

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????

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.