Search icon CANCEL
Subscription
0
Cart icon
Your Cart (0 item)
Close icon
You have no products in your basket yet
Save more on your purchases now! discount-offer-chevron-icon
Savings automatically calculated. No voucher code required.
Arrow left icon
Explore Products
Best Sellers
New Releases
Books
Videos
Audiobooks
Learning Hub
Conferences
Free Learning
Arrow right icon
Arrow up icon
GO TO TOP
Efficient Algorithm Design

You're reading from   Efficient Algorithm Design Unlock the power of algorithms to optimize computer programming

Arrow left icon
Product type Paperback
Published in Oct 2024
Publisher Packt
ISBN-13 9781835886823
Length 360 pages
Edition 1st Edition
Arrow right icon
Author (1):
Arrow left icon
Masoud Makrehchi Masoud Makrehchi
Author Profile Icon Masoud Makrehchi
Masoud Makrehchi
Arrow right icon
View More author details
Toc

Table of Contents (21) Chapters Close

Preface 1. Part 1: Foundations of Algorithm Analysis
2. Chapter 1: Introduction to Algorithm Analysis FREE CHAPTER 3. Chapter 2: Mathematical Induction and Loop Invariant for Algorithm Correctness 4. Chapter 3: Rate of Growth for Complexity Analysis 5. Chapter 4: Recursion and Recurrence Functions 6. Chapter 5: Solving Recurrence Functions 7. Part 2: Deep Dive in Algorithms
8. Chapter 6: Sorting Algorithms 9. Chapter 7: Search Algorithms 10. Chapter 8: Symbiotic Relationship between Sort and Search 11. Chapter 9: Randomized Algorithms 12. Chapter 10: Dynamic Programming 13. Part 3: Fundamental Data Structures
14. Chapter 11: Landscape of Data Structures 15. Chapter 12: Linear Data Structures 16. Chapter 13: Non-Linear Data Structures 17. Part 4: Next Steps
18. Chapter 14: Tomorrow’s Algorithms 19. Index 20. Other Books You May Enjoy

Beyond the master theorem – the Akra-Bazzi method

In the previous section, we discussed the limitations of the master theorem in solving recurrence functions. Although the master theorem can address a wide range of problems and is the most common approach, it does have its constraints. For example, it only applies to a specific class of divide-and-conquer recurrence functions:

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><mrow><mrow><mrow><mi>T</mi><mo>(</mo><mi>n</mi><mo>)</mo><mo>=</mo><mi>a</mi><mi>T</mi><mo>(</mo><mi>n</mi><mo>/</mo><mi>b</mi><mo>)</mo><mo>+</mo><mi>f</mi><mo>(</mo><mi>n</mi><mo>)</mo></mrow></mrow></mrow></math>

Here, the subproblem sizes are equal (<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><mml:mi>n</mml:mi><mml:mo>/</mml:mo><mml:mi>b</mml:mi></mml:math>). As we showed in the previous section, we can solve special cases of subtracting recurrence functions using the master theorem. It also has limitations on the form of the function <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><mml:mi>f</mml:mi><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>)</mml:mo></mml:math>. Specifically, the master theorem struggles with the following:

  • Unequal subproblem sizes: The recurrence splits into subproblems of significantly different sizes
  • More complex splitting: There are more than two subproblems in the recursion
  • Non-polynomial work: The function <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><mml:mi>f</mml:mi><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>)</mml:mo></mml:math> representing the work done outside the recursive calls isn’t easily categorized as polynomial...
lock icon The rest of the chapter is locked
Register for a free Packt account to unlock a world of extra content!
A free Packt account unlocks extra newsletters, articles, discounted offers, and much more. Start advancing your knowledge today.
Unlock this book and the full library FREE for 7 days
Get unlimited access to 7000+ expert-authored eBooks and videos courses covering every tech area you can think of
Renews at $19.99/month. Cancel anytime