I am trying to write an O(n) divide and conquer algorithm to search for an integer in a n*n sorted matrix (numbers in each row (column) are ascending) and output its position in the matrix if it is found. I don't have a complete understanding of the divide and conquer method so if anyone could help on both of those fronts it would be greatly appreciated.
Writing a O(n) algorithm is easy: just loop through your entire matrix from start to end. It's not really a divide and conquer algorithm though.
For a divide and conquer you could use a binary search to find a certain element in your sorted matrix. Binary search is one of the easiest divide and conquer algorithms. Use Google for code example's.
> Writing a O(n) algorithm is easy: just [snip]
In an n*n matrix, that would be O(n^2).
Even if binary search is used on each row, it is O(nlogn)
There is an O(n) algorithm for a sorted matrix, but I don't
think it's divide and conquer, it's more like a smart walking
algorithm. I don't remember the exact details though.
> ... numbers in each row (column) are ascending ...
Does this mean that
1. all numbers in every row is ascending, or
2. all numbers in every row is ascending and that all number in the
first column is ascending, or
3. all numbers in every row is ascending and all numbers in every
column is acceding.
In either case I do not see how solving this by using divide and
conquer is a good idea.
If you implement a binary search using recursion, I guess the
algorithm can be called divide and conquer. Approach the problem
this way.
1. If the incoming matrix contain one element, check if it equals
your number and if it does return (i,j), else null.
2. divide the incoming matrix into four smaller matrices and
send the one that your number exists in on using this method.
Do not create new matrices, use pointers. The time complexity is
O(ln(n)). It would be a better to use binary search, but I guess this
is school exercise and in that context this makes since. For more
info, see
http://en.wikipedia.org/wiki/Recursion
http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm
http://en.wikipedia.org/wiki/Binary_search
> What is the solution for that recurrence relation?
I guess its something like this
T(n) = a*T(n/b)+c
= a*(a*T(n/b^2)+c)+c = a^2*T(n/b^2)+(a^1+a^0)*c
= a^k*T(n/(b^k)) + sum_{i=0..k-1} a^i
{we know that T(1)=1 => k=ln(n)/ln(b)}
= ((a+c-1)*a^(ln(n)/ln(b))-c)/(a-1)
where a,b, and c are constants. Then use induction to verify.
> The algorithm you suggested is T(n) = 3 * T(n/4) + 1.
Why the 3? The recursive algorithm is sent on only on one
of the four matrices. Should it not be T(n) = T(n/4) + 1?
> T(n) = Omega(n ^ log_4 3) ~= Omega(n ^ 0.7925)
We get a more general result if we take T(n) from reply 8 and let a<>1
T(n) = ((a+c-1)*a^(ln(n)/ln(b))-c)/(a-1) = {a<>1}
= ( (a+c-1) * n^(ln(a)/ln(b)) - c )/(a-1)
~ O(n^(ln(a)/ln(b)))
and if a=1 we must take the limit when a->1, which is as expected
T(n) = c*ln(n)/ln(b) + 1
~ O(ln(n))
The value can be in 3 possible locations.
E.g. Consider the matrix:
-4 -3 -2 -1 0 1 5
-3 -2 -1 0 1 2 6
-2 -1 5 2 3 4 7
4 6 7 8 9 10 11
5 7 8 9 10 11 12
8 9 10 11 12 13 14
9 10 11 12 13 14 15
The value 5 is in 3 different sub-squares.
Thus: T(n) = 3 * T(n/4) + 1
> The value can be in 3 possible locations.
Just when I thought that I had not missed anything regarding
this problem, but nooooo. You are right. :) Thanks.
> There is an O(n) algorithm for a sorted matrix, but I don't
> think it's divide and conquer, it's more like a smart walking
> algorithm.
I think following algorithm is O(n) if the matrix contains
O(n^2) elements and it is a walking algorithm. Let k be the
number, (i,j) be current index, and a(i,j) be a matrix value.
1. Make a binary search on first column for k or the first number
above and let (i,j) be that index.
2. If a(i,j)=k we are done, else step to next column, that is (i,j)'=(i,j+1)
3. If a(i-1,j)>=k then (i,j)'=(i-1,j) and resume at 3, else resume at 2.
Since this will at most step through n+m nodes we get a maximum
running time of N(ln(n)+2*n) = O(n).
> The theorem I referred to is more general still, allowing c to
> be a function f(n).
Cool.
If you are referring to http://mitpress.mit.edu/algorithms/
when writing CLR, I do not have one available and I am curious.
Without knowing anything about f(n) they should not be able to
get beyond
T(n) = n^(ln(a)/ln(b)) + sum_{i=0..ln(n)/ln(b)-1} a^i*f(n/b^i)
or did they?
Just want to point out an error in my matrix example.
Value "2 3 4 7" should be "6 7 8 9" but the example
is still valid. Here is the corrected matrix.
-4 -3 -2 -1 0 1 5
-3 -2 -1 0 1 2 6
-2 -1 5 6 7 8 9
4 6 7 8 9 10 11
5 7 8 9 10 11 12
8 9 10 11 12 13 14
9 10 11 12 13 14 15
Okay, here's the full theorem.
- Begin theorem -
Let a >= 1 and b >= 1 be constants, let f(n) be a function, and let T(n) be defined on the non-negative integers by the recurrence
T(n) = aT(n/b) + f(n)
where we interpret n/b to mean either floor(n/b) or ceil(n/b). Then T(n) can be bounded asymptotically as follows.
1. If f(n) = O(n^log_b(a - eps)) for some constant eps > 0, then T(n) = Theta(n^log_b a).
2. If f(n) = Theta(n^log_b a), then T(n) = Theta(n^(log_b a) lg n).
3. If f(n) = Omega(n^log_b(a + eps)) for some constant eps > 0, and if af(n/b)<= cf(n) for some constant c < 1 and all sufficiently large n, then T(n) = Theta(f(n)).
- End theorem -
They do point out that not all f are covered, but it gets most functions that come up in real-life situations.