File MasterTheorem.h

↰ Parent directory (ADS/algorithm)

The solutions of the recurrences of section 2.9, as orders of growth :math:` Theta( c^n n^p log^q n ( log log n )^r ) ` [see Growth]:

Definition (`ADS/algorithm/MasterTheorem.h`)

Program Listing for File MasterTheorem.h

Detailed Description

master( a , b , beta , k ) solves :math:` T( n ) = a T( n / b ) + Theta( n^beta log^k n ) , a >= 1, b > 1, by the Teorema 2.4: with :math: alpha = log_b a , it is :math: Theta( n^alpha ) ` if :math:` beta < alpha , :math: Theta( n^beta log^k n ) ` if :math:` beta > alpha , and for :math: beta = alpha ` :math:` Theta( n^alpha log^{k+1} n ) ` if k > -1, :math:` Theta( n^alpha log log n ) ` if k = -1, :math:` Theta( n^alpha ) ` if k < -1; with k = 0 it is the Teorema 2.2;
linear( a , beta ) solves :math:` T( n ) = sum_{i=1}^h a_i T( n - i ) + Theta( n^beta ) ` with :math:` a = sum_i a_i ` by the Teorema 2.5: :math:` Theta( n^{beta+1} ) ` if a = 1, and the upper bound :math:` O( a^n n^beta ) ` if a >= 2, which is not always tight (Fibonacci is :math:` Theta( phi^n ) ); the theorem has integer a_i, and for real a_i with 1 < a < 2 (e.g., T( n ) = 1.5 T( n - 1 ) + 1, :math: Theta( 1.5^n ) `) the recurrence is exponential as well, and linear() gives the same upper bound.

Two orders of growth compare as their functions do for n large: first by the base c of the exponential, then by the power p of n, then by the powers q and r of the logarithms, which gives the hierarchy :math:` O( 1 ) subset O( log n ) subset O( n ) subset O( n log n ) subset O( n^2 ) subset O( n^3 ) subset O( 2^n ) ; note that :math: 2^{log_2 n} = n ` is a polynomial, not an exponential, and that :math:` n^{log n} ` grows faster than every polynomial and slower than every :math:` c^n ` with c > 1, so that it has no place in this family.

The contracts [see File Contract.h]: a >= 1 and b > 1 for master(), a >= 1 for linear(). The functions are defined in MasterTheorem.tpp.