matrix algorithm

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

[RoboTact]

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

Right...

[kiuhnm]

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.

[TheCPUWizard]

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... Smacking Self... 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.

[ProgramThis]

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