Short answer is: there is no such thing as miracle.

The answer is already contained in the question. 1) The algorithm you show is really of the O(N

^{2}) complexity; 2) It can be improved but the complexity cannot grow lower then O(N

^{2}).

First, let's see why the complexity is O(N

^{2}). If you test all N

^{2} elements of the matrix, it gives you the said complexity. If you test not all of them, there is a chance of incorrect answer (false minimum) because any of the untested values can be less then the found value.

The real speed depends on the test set of values. That said, there is some probability that there is no less values, because you could sooner find the value of

`int.MinValue`

. In my solution below, this is taken into account. This line commented "questionable check" slightly reduce the complexity, but increase absolute time of the algorithm. Overall, it is useful only if the probability of

`int.MinValue`

in data is high enough. Generally, the real performance of any algorithm depends on the method of generation of data set.

Now, performance of your code could be improved by one mysterious trick:

`++j`

makes better performance then

`j++`

. I avoided

`for`

loops by using

`foreach`

, please see below. Believe or not, it works correctly for multidimensional arrays.

Also, you need to fix a bug. You 100 is a bug, not even a bug, just foolishness. Real solution is using

`int.MaxValue`

. For floating point types, you should have used

`+Inf`

which correctly compares with other floating point values.

So, here is the fixed solution:

internal static int Minimum(int[,] matrix) {
int result = int.MaxValue; foreach(int value in matrix) {
if (value == int.MinValue) return value; if (value < result)
result = value;
} return result;
}

—SA