-1

We are given array A[1..n][1..n] and value X. We will call an array increasing if it complies the following:
for every k,l A[k][l] >= A[i][j], where i <= k, j <= l.
We are also given the fact, that A is increasing.

Task is to prove, that there isn't an algorithm which is able to determine if X is an element of A in less than N comparisons.

I found myself completely stuck with that one, so I would appreciate any help.

Dmitri K
  • 331
  • 1
  • 12
  • 2
    Sounds like homework... – Emily L. Mar 11 '14 at 18:21
  • 1
    This sounds more like math question. Proving stuff doesn't exist isn't really software engineering. – Sopuli Mar 11 '14 at 18:23
  • All you need is 1 counter-example. Take a 2x2 array where `A[0][0]=10` and `A[1][1]=40` and you are asked whether or not `A` contains 25. It's only a few steps to show that you MUST check at least 2 elements, thereby showing that no such algorithm exists that can do it in less than N=2 comparisons. – Matt Mar 11 '14 at 18:30
  • You can find the proof [here](http://stackoverflow.com/q/10589975/1009831) or [here](http://twistedoakstudios.com/blog/Post5365_searching-a-sorted-matrix-faster). – Evgeny Kluev Mar 11 '14 at 18:42
  • @Sopuli "Proving stuff doesn't exist isn't really software engineering." WTF!!! – imreal Mar 11 '14 at 19:00
  • 2
    @Nick Coming up with a solution that solves the task is software engineering. Coming up with proof that certain solution cannot (or can) be found is math science. And if you want to discuss proving theorems, SO might not be the right forum for it. My 5c. – Sopuli Mar 11 '14 at 19:22
  • @Matt How can showing an instance that does not violate the statement proving in general the statement is correct? For eg, I would like to prove "everyday is not a raining day", I cannot say because today is not a raining day, QED, can I? – shole Mar 12 '14 at 03:45
  • @shole No, you can't conclude that "everyday is not a raining day", but what you can prove is that it is false by one rainy day. Likewise, let P be the statement "There exists an algorithm to determine if X is an element of A in less than N comparisons." The 2x2 example requires at least 2 comparisons, proving that P is false. Therefore, "there isn't an algorithm which is able to determine if X is an element of A in less than N comparisons." QED – Matt Mar 12 '14 at 04:46
  • @Matt I see...seems valid, I just didn't feel right when I come to that raining example, as even we proved "everyday is not rainning" false does not mean "everyday is raining" is true...that's why I threw the question... BTW, do you think using M.I. works for this problem? like assuming x cannot be found within n steps for A[n][n], then for an increasing array A[n+1][n+1], I can verify x with at least (by two binary search?) n + (2log(n-1) + 1) steps >= n+1 steps , QED.. is this valid too? – shole Mar 12 '14 at 05:01
  • @shole I'm not exactly sure what you mean by two binary searches, but it seems that you are talking about a *specific* algorithm, so in the best case that proof would only show that particular algorithm would require more than n steps. It doesn't seem to generalize to showing that no such algorithm exists. I apologize in advance if I have misunderstood your point. – Matt Mar 12 '14 at 05:14
  • 1
    This question appears to be off-topic because it is about Math, not Programming. – Ray Cheng Mar 12 '14 at 15:45

2 Answers2

2

I prove that at least for one matrix you have a worst case of n comparisons, for that purpose I create a specific matrix A.

Consider the diagonal line from A[1][n] to A[n][1], this includes all values 

A[i][j] for i+j=n+1

Set all elements to the left of that diagonal to 0:

A[i][j]=0 for i+j<n+1

and all remaining elements, including the diagonal itself, to 2:

A[i][j]=2 for i+j>=n+1

As you can easily check this is a valid matrix according to the required conditions. Now you can set any value on the diagonal to 1:

A[z][n+1-z] = 1

The result then looks like this:

0 0 0 2
0 0 2 2
0 1 2 2
2 2 2 2

This remains a valid matrix. Now search for X=1. In order to check if any value on the diagonal is 1 you have to look at each one, because they are independent. There are n values on the diagonal, you have to check each one in order to find the 1, so you need to do n comparisons.

pentadecagon
  • 4,717
  • 2
  • 18
  • 26
  • Though links provided by EvgenyKluev were extreamly helpful and gave a lot of info about more general problem, I'm not gonna flag question as duplicate and gonna accept this answer t since it addresses my specific problem. – Dmitri K Mar 12 '14 at 06:11
0

A variation on @pentadecagon: you are free to set N arbitrary values on the diagonal, in some range min..max containing X, and fill the rest of the array with lower than min on one side and higher than max on the other.

The values on the sides can't give you information on the location of X, and the N values give no information on each other. So you need to search among N unsorted elements.