[gregoryH]

alcdotcom, on 6 Mar, 2007 - 04:22 AM, said:

I think this problem is down for the count at O(n log n).

Hi

I have to agree that the given algorithm is at best O(log n), O(n log n) worst.

O(n) is really for a piece of very straight forward code, with perhaps a single loop to process some data.

regards


Greg

[maj0ra]

We've had a discussion at work:

currentRow = first row
(1) linearly search along currentRow until you find a 0.
(2) linearly search down the column that contains that 0 until you find a 1, set currentRow to the row the 1 is in.
(3) goto (1).
currentRow is now the row with most 1s.


1 1 0 0 0 0

1 1 1 1 0 0

1 1 1 0 0 0

1 1 1 1 1 0

1 1 1 0 0 0


Hopefully the ASCII art comes out okay. (Edit : It didn't so I've boldened the ones that are visited)

Worse case scenario; this involves n horizontal and n vertical moves, so a worst case of O(2n) == O(n)

This post has been edited by maj0ra: 13 April 2007 - 04:07 AM

[NickDMax]

nice

[Programmist]

Fantastic.