Wrox Programmer Forums Big-O Analysis Example
 Register | FAQ | Members List | Calendar | Search | Today's Posts | Mark Forums Read
BOOK Programming Interviews Exposed: Secrets to Landing Your Next Job 2nd Ed ISBN: 978-0-470-12167-2
 This is the forum to discuss the Wrox book Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition by John Mongan, Noah Suojanen, Eric Gigučre; ISBN: 9780470121672 Read more about Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition or buy the book from your favorite retailer Download the code for Programming Interviews Exposed: Secrets to Landing Your Next Job, 2nd Edition
 Welcome to the p2p.wrox.com Forums. You are currently viewing the BOOK Programming Interviews Exposed: Secrets to Landing Your Next Job 2nd Ed ISBN: 978-0-470-12167-2 section of the Wrox Programmer to Programmer discussions. This is a community of tens of thousands of software programmers and website developers including Wrox book authors and readers. As a guest, you can read any forum posting. By joining today you can post your own programming questions, respond to other developers’ questions, and eliminate the ads that are displayed to guests. Registration is fast, simple and absolutely free .
July 7th, 2011, 01:15 AM
 Registered User Join Date: Jul 2011 Posts: 1 Thanks: 0 Thanked 0 Times in 0 Posts
Big-O Analysis Example

Hi All,

I'm working through one of the examples in the Big-O Analysis section, in which they analyze the CompareToAll implementation that returns the largest integer in an array. The book states:

"For now, assume that the maximum element is at the end of the array. In this case, this function may compare each of n elements to n other elements. Thus, there are n ( n examinations, and this is an O( n 2 ) algorithm."

However, the outer for loop checks the end of the array first, so wouldn't the inner loop just run through once before the method breaks out of the outer for loop, making it just n examinations?

Thanks for helping me clarify this!
July 23rd, 2011, 11:14 AM
Authorized User
 Points: 68, Level: 1
 Activity: 0%

Join Date: May 2011
Posts: 15
Thanks: 11
Thanked 0 Times in 0 Posts
Chapter 3, p. 22, of 2nd edition

Yes, you're right, as I see it.

This idea could be better expressed in a future edition. Instead of writing "at the end of the array", it would be better to write "the last element to be examined by the algorithm: here it would be the element at index zero".

Hope this helps!

Wayne

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is OffTrackbacks are Off Pingbacks are On Refbacks are Off

 Similar Threads Thread Thread Starter Forum Replies Last Post Do you use Analysis Services? valiko_work SQL Server 2005 0 August 10th, 2007 06:41 AM Further analysis migake XSLT 3 November 6th, 2006 07:13 PM Crystal Analysis SaralaManoharan Classic ASP Professional 0 December 21st, 2005 08:36 AM Analysis Manager ColdFusionRO SQL Server 2000 1 July 25th, 2003 06:39 PM TOP N Analysis rj SQL Server 2000 1 July 13th, 2003 11:21 PM

All times are GMT -4. The time now is 03:20 PM.