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 > > > > -- --
