Wrox Programmer Forums

Need to download code?

View our list of code downloads.

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
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 .
DRM-free e-books 300x50
Reply
 
Thread Tools Display Modes
  #1 (permalink)  
Old July 7th, 2011, 12:15 AM
Registered User
 
Join Date: Jul 2011
Posts: 1
Thanks: 0
Thanked 0 Times in 0 Posts
Default 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!
Reply With Quote
  #2 (permalink)  
Old July 23rd, 2011, 10:14 AM
Authorized User
Points: 68, Level: 1
Points: 68, Level: 1 Points: 68, Level: 1 Points: 68, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: May 2011
Posts: 15
Thanks: 11
Thanked 0 Times in 0 Posts
Default 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
Reply With Quote
Reply


Thread Tools
Display Modes

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 Off
Trackbacks 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 05:41 AM
Further analysis migake XSLT 3 November 6th, 2006 06:13 PM
Crystal Analysis SaralaManoharan Classic ASP Professional 0 December 21st, 2005 07:36 AM
Analysis Manager ColdFusionRO SQL Server 2000 1 July 25th, 2003 05:39 PM
TOP N Analysis rj SQL Server 2000 1 July 13th, 2003 10:21 PM



All times are GMT -4. The time now is 08:41 PM.


Powered by vBulletin® Version 3.7.0
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
© 2013 John Wiley & Sons, Inc.