@Don : your algo time complexity is O(n^2)
It can be reduced to this :-
// Now look for largest square with top left corner at (i,j)
for(i = 0; i < n; ++i)
for(j = 0; j < n; ++j)
{
s = Min(countRight[i][j], countDown[i][j]);
if (countRight[i][j] && countDown[i][j] &&
(countRight[i+s][j] >= s) && (countDown[i][j+s] >= s) && s>max)
{
bestI = i; bestJ = j; max = s;
}
}
On 1/25/13, Don <[email protected]> wrote:
> The worst case I know of is when the matrix is solid black except for
> the lower right quadrant. In this case, it does break down into O(n^3)
> runtime. It took about 8 times as long to run n=4000 as it took for
> n=2000.
> Don
>
> On Jan 24, 10:29 am, Don <[email protected]> wrote:
>> I'm not sure I understand your case. However, I stated that there are
>> cases where it is worse than O(N^2). The runtime is highly dependent
>> on the contents of the matrix. In many cases it takes fewer than N^2
>> iterations. Occasionally it takes more. On average it seems to be
>> roughly O(N^2), but again that depends a lot on what is in the matrix.
>> I got that result by trying different ways of filling the matrix. I
>> tried things like randomly setting each pixel with various
>> probabilities, placing random horizontal and vertical segments,
>> placing random squares, or placing random filled squares. I did all of
>> those both in black on white and white on black. In all of those
>> cases, going from n=1000 to n=2000 resulted in a runtime increase of
>> less than a factor of 4.
>>
>> Don
>>
>> On Jan 23, 10:33 pm, bharat b <[email protected]> wrote:
>>
>>
>>
>>
>>
>>
>>
>> > @Don: the solution is very nice.. But, how can u prove that it is
>> > O(n^2)..
>> > for me it seems to be O(n^3) ..
>>
>> > Ex: nxn matrix .. all 1s from (n/2,0) to (n/2,n/2).
>> > all 1s from (n/2,0) to (n,0).
>>
>> > On Thu, Jan 17, 2013 at 9:28 PM, Don <[email protected]> wrote:
>> > > The downside is that it uses a bunch of extra space.
>> > > The upside is that it is pretty fast. It only does the time-consuming
>> > > task of scanning the matrix for contiguous pixels once, it only
>> > > searches for squares larger than what it has already found, and it
>> > > doesn't look in places where such squares could not be. In practice
>> > > it
>> > > performs at O(n^2) or better for most inputs I tried. But if you are
>> > > devious you can come up with an input which takes longer.
>> > > Don
>>
>> > > On Jan 17, 10:14 am, marti <[email protected]> wrote:
>> > > > awesome solution Don . Thanks.
>>
>> > > > On Thursday, January 17, 2013 12:38:35 AM UTC+5:30, marti wrote:
>>
>> > > > > Imagine there is a square matrix with n x n cells. Each cell is
>> > > > > either
>> > > > > filled with a black pixel or a white pixel. Design an algorithm
>> > > > > to
>> > > find the
>> > > > > maximum subsquare such that all four borders are filled with
>> > > > > black
>> > > pixels;
>> > > > > optimize the algorithm as much as possible
>>
>> > > --
>
> --
>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
