# Algorithm analysis help

• (2 Pages)
• 1
• 2

## 18 Replies - 10294 Views - Last Post: 16 April 2007 - 02:48 PM

### #16 gregoryH

Reputation: 60
• Posts: 656
• Joined: 04-October 06

## Re: Algorithm analysis help

Posted 05 April 2007 - 06:48 AM

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

### #17 maj0ra

Reputation: 1
• Posts: 5
• Joined: 12-April 07

## Re: Algorithm analysis help

Posted 13 April 2007 - 03:59 AM

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

### #18 NickDMax

Reputation: 2255
• Posts: 9,245
• Joined: 18-February 07

## Re: Algorithm analysis help

Posted 13 April 2007 - 04:36 AM

nice

### #19 Programmist

• Refactorer in Chief

Reputation: 255
• Posts: 1,843
• Joined: 02-January 06

## Re: Algorithm analysis help

Posted 16 April 2007 - 02:48 PM

Fantastic.