Algorithm analysis help

  • (2 Pages)
  • +
  • 1
  • 2

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

#16 gregoryH  Icon User is offline

  • D.I.C Addict
  • member icon

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

Re: Algorithm analysis help

Posted 05 April 2007 - 06:48 AM

View Postalcdotcom, 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
Was This Post Helpful? 0
  • +
  • -

#17 maj0ra  Icon User is offline

  • New D.I.C Head

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

Re: Algorithm analysis help

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

Was This Post Helpful? 1
  • +
  • -

#18 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Algorithm analysis help

Posted 13 April 2007 - 04:36 AM

nice
Was This Post Helpful? 0
  • +
  • -

#19 Programmist  Icon User is offline

  • CTO
  • member icon

Reputation: 252
  • View blog
  • Posts: 1,833
  • Joined: 02-January 06

Re: Algorithm analysis help

Posted 16 April 2007 - 02:48 PM

Fantastic. :^:
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2