Introduction to The designAnalysis of Algorithms3 RD EDITIONVice President and editorial director ecs Marcia hortonEditor-in-Chief Michael hirschAcquisitions editor Matt GoldsteinEditorial assistant Chelsea bellVice President, Marketing Patrice JonesMarketing Manager Yezan AlayanSenior marketing coordinator Kathryn ferrantiMarketing assistant Emma sniderVice president production vince o'brienManaging Editor Jeff HolcombProduction Project Manager Kayla Smith-TarboxSenior Operations Supervisor Alan FischerManufacturing buyer Lisa McDowellArt Director Anthony gemmellaroText Designer Sandra rigneyCover Designer Anthony GemmellaroCover Illustration Jennifer KohnkeMedia editor daniel sandinFull-Service Project Management Windfall SoftwareComposition Windfall Software, using ZzTEXPrinter/Binder Courier westfordCover Printer Courier WestfordText font Times tenCopyright o 2012, 2007, 2003 Pearson Education, Inc, publishing as Addison-Wesley. All rightsreserved. Printed in the United States of America. This publication is protected by Copyrightand permission should be obtained from the publisher prior to any prohibited reproduction,storage in a retrieval system, or transmission in any form or by any means, electronic, mechanicalphotocopying, recording, or likewise. To obtain permission(s)to use material from this work,please submit a written request to Pearson Education, Inc, Permissions Department, One lakeStreet, Upper Saddle river, New Jersey 07458, or you may fax your request to 201-236-3290This is the e Book of the printed book and may not include any media, Website access codes orprint supplements that may come packaged with the bound bookMany of the designations by manufacturers and sellers to distinguish their products are claimedas trademarks. Where those designations appear in this book, and the publisher was aware of atrademark claim, the designations have been printed in initial caps or all capsLibrary of Congress Cataloging-in-Publication DataLevitin, ananIntroduction to the design analysis of algorithms / Anany Levitin -3rd edIncludes bibliographical references and indexISBN-13:978-0-13-231681-1ISBN-10:0-13-231681-11. Computer algorithms. I. Title. II. Title: Introduction to the design and analysis calgorithQA76.9A43L482012005.1—dc2320110270891514131211CRW-10987654321ISBN10:0-13-231681-1PEARSONISBN13:978-0-13-231681-1Introduction to The DesignAnalysis of Algorithms3RD EDITIONAnany LevitinVillanova universityPEARSONBoston Columbus Indianapolis New York San Francisco Uppcr Saddle Riveredam Cape lown IJubai I ondon Madrid Milan Munich Paris Montreal torontoDelhi Mexico City Sio Paulo Sydney Hong Kong Seoul Singapore 'Taipei TokyoThis page intentionally left blankBrief Contentshe Third ediPrefaceXIX2 Fundamentals of the Analysis of Algorithm Effici3 Brute Force and Exhaustive Search4 Decrease-and-Conquer135 Divide-and-Conquer1696 Transf2012538 Dynamic Programming2839 Gree3151 Limitations of Algorithm Pc12 Coping with the Limitations of Algorithm PowerUseful Formulas for the Analysis of AlgorithmsPPENDIX BShort tutorial on recurrence relationsReferencesHints to exercis503IndexThis page intentionally left blankContentsNew to the third editionPrefacemic Problem Solving9Understanding the ProblemAscertaining the Capabilities of the Computational Deviceact and Approximate Problem Solrithm and Data stMethods of specifyAlgorithm3 Important Problem type132021i1.4 Fundamental Data StructuresLinear data structuresGraphsSets and dictionaries2 Fundamentals of the Analysis of Algorithm1 The AnalysisMeUnits for Measuring Running TimeOrders of growthiorst-Case, Best-Case, and Average-Case EfficienciesRecapitulation of the Analysis framework2.2 Asymptotic Notations and Basic Efficiency Classes52Informal IntroductionO-notation22-notationful Property Involving the Asymptotic notaing OrdExercises 2.22.3 Mathematical Analysis of Nonrecursive algorithms2. 4 Mathematical Analysis of Recursive Algorithms2.5 Example: Computing the nth Fibonacci Number2.6 Empirical Analysis of Algorithms2.62.7 Algorithm Visualization