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 3rd Edition
This is the forum to discuss the Wrox book Programming Interviews Exposed: Secrets to Landing Your Next Job, 3rd Edition by John Mongan, Noah Kindler, Eric Giguere; ISBN: 978-1-118-26136-1
Welcome to the p2p.wrox.com Forums.

You are currently viewing the BOOK Programming Interviews Exposed: Secrets to Landing Your Next Job 3rd Edition 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 March 5th, 2013, 02:37 AM
Registered User
Points: 30, Level: 1
Points: 30, Level: 1 Points: 30, Level: 1 Points: 30, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Mar 2013
Posts: 7
Thanks: 0
Thanked 0 Times in 0 Posts
Default Big-O CompareToAll

Hi,

On page 25, the CompareToAll function is stated to be O(n^2), but I cannot see how that can be. Is it possible that the "break" statement added after "isMax=false;" should not be there? If that was removed, this algorithm is clearly O(n^2) for me, otherwise, it seems to be O(n).

Thank you,
Erich
Reply With Quote
  #2 (permalink)  
Old March 5th, 2013, 07:12 AM
Wrox Author
Points: 51, Level: 1
Points: 51, Level: 1 Points: 51, Level: 1 Points: 51, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Oct 2012
Posts: 10
Thanks: 0
Thanked 1 Time in 1 Post
Default

No, it's definitely O(n^2) whether the break statement is there or not. There is a detailed discussion of why this is so near the bottom of page 26.

Remember that CompareToAll is a very dumb algorithm and it was designed specifically to demonstrate Big-O analysis.

In general, any time you have a nested loop where each loop depends on n then you have an algorithm that is at least O(n^2)....

Eric
Reply With Quote
  #3 (permalink)  
Old March 5th, 2013, 03:10 PM
Registered User
Points: 30, Level: 1
Points: 30, Level: 1 Points: 30, Level: 1 Points: 30, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Mar 2013
Posts: 7
Thanks: 0
Thanked 0 Times in 0 Posts
Default

That confuses me. Say the biggest number is at the very beginning. The first loop walks backwards and the second loop walks forwards.

Say the numbers are 7 3 5 4 2

On our first loop pass, array[i] =2.

array[0] = 7. This is greater than array[i], and will assign isMax to false and immediately break.

We then proceed to array[i] = 4
array[0]=7. Again, break.

We continue in this fashion n times, not n^2. Unless the break is removed....
Reply With Quote
  #4 (permalink)  
Old March 8th, 2013, 04:40 PM
Registered User
Points: 30, Level: 1
Points: 30, Level: 1 Points: 30, Level: 1 Points: 30, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Mar 2013
Posts: 7
Thanks: 0
Thanked 0 Times in 0 Posts
Default

Hi I have not seen a reply to this, and I am fairly confident that the text is incorrect.

I decided to code it verbatim and run the algorithm just to verify my sanity. I added a counter in the inner for loop to keep count of course.

I want to clarify that I am stating that the text is incorrect in stating that the time is O(n) when the maximum element is in the beginning or at the end of the array. HOWEVER, I agree that the worst case runtime is still O(n^2) with the maximum element being in the middle and the first half of the elements are less than the last half of the elements. Still, the text is incorrect in this case as it defines the more precise runtime at (n^2)/2 when it is in fact (n/2)^2+n. The reason again for this error here is what I believe the presumable inclusion of a typo in the code that includes the "break" in the inner for loop.

Could you please check over the code to see if it is a typo with the text? We can speak privately if you do not agree, as I cannot see how the text can be right.
Reply With Quote
  #5 (permalink)  
Old March 11th, 2013, 02:34 AM
Wrox Author
Points: 21, Level: 1
Points: 21, Level: 1 Points: 21, Level: 1 Points: 21, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Oct 2012
Posts: 8
Thanks: 0
Thanked 0 Times in 0 Posts
Default

I do apologize, there are some issues with this section. At some point after the first edition of the book, it appears that the code was "optimized" and no longer clearly illustrates the points of best, worst and average case performance as it should.

At the bottom of page 26, it says: "For now, assume that the maximum element is at the beginning of the array." This should be end of the array. Also it says: "Thus there are n∑n examinations so this is an O(n) algorithm." Obviously this should read: "Thus there are n∑n examinations so this is an O(n^2) algorithm."

The code should look like:
Code:
/* Returns the largest value in an array of non-negative integers */
int CompareToAll(int array[], int n) 
{
  int i, j;
  bool isMax;
  /* Make sure that there is at least one element in the array. */
  if (n <= 0)
    return -1;

  for (i = 0; i < n; i++) {
    isMax = true;
    for (j = 0; j < n; j++) {
      /* See if any value is greater. */
      if (array[j] > array[i]) {
        isMax = false; /* array[i] is not the largest value. */
      }
    }
    /* If isMax is true, no larger value exists; array[i] is max. */
    if (isMax)
      return array[i];
    }
}
The above code matches the discussion on page 27, while the code printed in the book doesn't. (The code printed in the book has best case performance of O(n) when the largest value is at the beginning or end of the array and average and worst case performance of O(n^2), although the calculation of the average and worst cases doesn't quite match what's in the text.)

Again apologies for this confusion and thanks for your persistence in getting this cleared up.

--John
Reply With Quote
  #6 (permalink)  
Old March 11th, 2013, 02:49 AM
Registered User
Points: 30, Level: 1
Points: 30, Level: 1 Points: 30, Level: 1 Points: 30, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Mar 2013
Posts: 7
Thanks: 0
Thanked 0 Times in 0 Posts
Default

Thank you for getting back on this
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
How big is too big? chroniclemaster1 XML 5 September 17th, 2012 02:07 AM
Big disappointment SharePointer BOOK: Workflow in SharePoint 2010: Real World Business Workflow Solutions 1 April 2nd, 2012 07:00 AM
First big errata m0y BOOK: Beginning Python: Using Python 2.6 and Python 3.1 3 December 6th, 2011 07:49 PM
Big-O Analysis Example JebCrowder BOOK Programming Interviews Exposed: Secrets to Landing Your Next Job 2nd Ed ISBN: 978-0-470-12167-2 1 July 23rd, 2011 11:14 AM
Big Query hortoristic SQL Server 2000 3 May 25th, 2004 05:01 PM



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


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