File AkraBazzi.h

↰ Parent directory (ADS/algorithm)

The recurrences of divide et impera with parts of different sizes, :math:` T( n ) = sum_{i=1}^k a_i T( b_i n ) + g( n ) , a_i > 0 and 0 < b_i < 1, which the master theorem [see :ref:`file_ADS_algorithm_MasterTheorem.h] does not cover when the b_i differ, e.g.

Definition (ADS/algorithm/AkraBazzi.h)

Detailed Description

:math:` T( n ) = T( n / 5 ) + T( 7 n / 10 ) + n ` of the selection in linear time.

By the theorem of Akra and Bazzi, with p the unique real root of :math:` sum_i a_i b_i^p = 1 `, :math:`[
T( n ) = Thetaleft( n^p left( 1 + int_1^n

frac{g( u )}{u^{p+1}} du right) right) ,

` and for :math:` g( n ) = Theta( n^beta log^k n ) ` the integral gives the cases of the master theorem with p for :math:` log_b a : :math: Theta( n^p ) ` if :math:` beta < p , :math: Theta( n^beta log^k n ) ` if :math:` beta > p , and for :math: beta = p ` :math:` Theta( n^p log^{k+1} n ) ` if k > -1, :math:` Theta( n^p log log n ) ` if k = -1, :math:` Theta( n^p ) ` if k < -1. The floors and the ceilings of the sizes, and perturbations of :math:` O( n / log^2 n ) `, do not change the order (Leighton).

akraBazziExponent() finds p by bisection: :math:` f( p ) = sum_i a_i b_i^p ` is strictly decreasing, so a bracket found by doubling and 200 halvings give p to the precision of a double; akraBazzi() then returns the order as a Growth.

The contracts [see File Contract.h]: at least one term, a_i > 0 and 0 < b_i < 1; p is a root of the equation to 1e-9. The functions are defined in AkraBazzi.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 2.9, https://algoritmicamente.it/materiali/libro/capitoli/cap02.pdf

  1. Akra, L. Bazzi, On the solution of linear recurrence equations, Computational Optimization and Applications 10(2), 195-210, 1998, doi:10.1023/A:1018373005182

  1. Leighton, Notes on better master theorems for divide-and-conquer recurrences, MIT, 1996

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions