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 June 2nd, 2013, 11:23 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 Pg 132 Merge sort Master directory

The solution states that the final step of the merge sort can perform this in O(n) time, but I am pretty sure this is incorrect.

The answer should be O(nlogk) where k is the # of departmental directory servers.

Am I reading this wrong?
Reply With Quote
  #2 (permalink)  
Old July 11th, 2017, 04:03 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

You are correct. If you're clever about how you find the next element to merge (use a heap consisting of the next element from each of the lists you're merging), then it's O(n log k) as you state. If you're less clever and scan the next element of each list to find the next element to merge, then it's O(n k).

John
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
Merge Sort C source code yulin11 Visual C++ 1 October 7th, 2012 11:21 AM
Chapter 4 - pg 156 - master page... richv BOOK: Beginning SharePoint 2010 Development 3 March 23rd, 2011 04:35 AM
ASP.NET Master Page Problem with Virtual Directory Alias kwilliams ASP.NET 4 General Discussion 1 March 3rd, 2011 04:55 AM
Pg.84 Last Paragraph - master detail report/product name waylock BOOK: Beginning Oracle Application Express ISBN: 9780470388372 2 November 20th, 2009 02:45 PM
Customer Support Site Master Pg. Meta Tags taggiese BOOK: ASP.NET 2.0 Instant Results ISBN: 978-0-471-74951-6 4 February 26th, 2007 10:35 PM



All times are GMT -4. The time now is 10:40 PM.


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