Program Listing for File MasterTheorem.h

↰ Return to documentation for file (ADS/algorithm/MasterTheorem.h)

/*--------------------------------------------------------------------------*/
/*-------------------------- File MasterTheorem.h --------------------------*/
/*--------------------------------------------------------------------------*/
/*--------------------------------------------------------------------------*/
/*----------------------------- DEFINITIONS --------------------------------*/
/*--------------------------------------------------------------------------*/

#ifndef __ADS_MasterTheorem
 #define __ADS_MasterTheorem
                      /* self-identification: #endif constant */

/*--------------------------------------------------------------------------*/
/*------------------------------ INCLUDES ----------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/Contract.h"

#include <cmath>
#include <compare>
#include <utility>

/*--------------------------------------------------------------------------*/
/*--------------------------- NAMESPACE ------------------------------------*/
/*--------------------------------------------------------------------------*/

namespace ADS {

struct Growth {
 double c = 1;
 double p = 0;
 double q = 0;
 double r = 0;
 bool upper = false;

 [[nodiscard]] double at( double n ) const {
  return( std::pow( c , n ) * std::pow( n , p ) * std::pow( std::log( n ) , q )
          * std::pow( std::log( std::log( n ) ) , r ) );
  }

 friend std::partial_ordering operator<=>( const Growth & a ,
                                           const Growth & b ) {
  for( auto [ x , y ] : { std::pair( a.c , b.c ) , std::pair( a.p , b.p ) ,
                          std::pair( a.q , b.q ) , std::pair( a.r , b.r ) } )
   if( x != y )
    return( x <=> y );
  return( std::partial_ordering::equivalent );
  }

 friend bool operator==( const Growth & a , const Growth & b ) {
  return( ( a <=> b ) == 0 );
  }
 };

inline Growth master( double a , double b , double beta , double k = 0 );

inline Growth linear( double a , double beta );

/*--------------------------------------------------------------------------*/

}  // end( namespace ADS )

/*--------------------------------------------------------------------------*/
/*-------------------------- IMPLEMENTATION --------------------------------*/
/*--------------------------------------------------------------------------*/

#include "ADS/algorithm/impl/MasterTheorem.tpp"

/*--------------------------------------------------------------------------*/

#endif  /* MasterTheorem.h included */

/*--------------------------------------------------------------------------*/
/*------------------------ End File MasterTheorem.h ------------------------*/
/*--------------------------------------------------------------------------*/