Balancing Is Not Always Good (Classic Reprint) - Softcover

Inhaltsangabe

Optimal splitting and tree structure shape algorithm performance. This book introduces practical tools for analyzing how recurrences describe the running time of divide-and-conquer algorithms. It connects differences, convexity, and concavity to the way work is distributed as n grows, and shows how to frame these ideas with binary trees.

Two clear sections frame the value: first, a set of theorems that describe when simple, balanced structures minimize cost; and second, a deeper look at how different tree shapes—balanced or heap-like—affect the f-sum and the overall solution to core recurrence relations. Throughout, the text stays focused on concrete results and their implications for algorithm design.

• Learn how first- and second-order differences relate to monotonicity, convexity, and cost.


• See how balanced and heap trees influence minimal f-sum in recurrences.


• Explore when the optimal strategy is to split evenly versus becoming more unbalanced.


• Understand error estimates that compare rational-domain solutions to integer-domain recurrences.

Ideal for readers of advanced algorithms, discrete math, and performance analysis who want a rigorous, application-oriented treatment of recurrence relations and tree-based costs.

Die Inhaltsangabe kann sich auf eine andere Ausgabe dieses Titels beziehen.