Comparison of running times

Taken from page 15 of Introduction to Algorithms 3ed, for each function f(n) and time t in the following table, we determine the largest size n of a problem that can be solved in time t, assuming the algorithm to solve the problem takes f(n) microseconds.

	1 second	1 minute	1 hour	1 day	1 month	1 year	1 century
lg n	inf	inf	inf	inf	inf	inf	inf
√n	824,633,720,832	3.3776997205279E+15	1.3835058055282E+19	7.0835497243045E+21	7.2535549176878E+24	9.2845502946404E+26	7.6059036013694E+30
n	786,432	50,331,648	3,221,225,472	103,079,215,104	3,298,534,883,328	26,388,279,066,624	3.3776997205279E+15
n lg n	49,152	3,145,728	100,663,296	3,221,225,472	103,079,215,104	824,633,720,832	52,776,558,133,248
n²	768	6,144	49,152	393,216	1,572,864	6,291,456	50,331,648
n³	96	384	1,536	6,144	12,288	24,576	196,608
2ⁿ	24	24	24	48	48	48	48
n!	12	12	12	12	12	24	24

The above table generated with the following code:

<?php

define( 'MICROSECOND',  0.000001      );
define( 'SECOND',       1.0           );
define( 'MINUTE',       60.0 * SECOND );
define( 'HOUR',         60.0 * MINUTE );
define( 'DAY',          24.0 * HOUR   );
define( 'MONTH',        30.0 * DAY    );
define( 'YEAR',         365.0 * DAY   );
define( 'CENTURY',      100.0 * YEAR  );

$spec = [
  'second'  => SECOND,
  'minute'  => MINUTE,
  'hour'    => HOUR,
  'day'     => DAY,
  'month'   => MONTH,
  'year'    => YEAR,
  'century' => CENTURY,
];

main();

function main() {
  global $spec;
  $data = [
    'lg n'   => calc( function( $n ) { return lg( $n ); } ),
    '√n'     => calc( function( $n ) { return sqrt( $n ); } ),
    'n'      => calc( function( $n ) { return $n; } ),
    'n lg n' => calc( function( $n ) { return $n * lg( $n ); } ),
    'n²'     => calc( function( $n ) { return $n * $n; } ),
    'n³'     => calc( function( $n ) { return $n * $n * $n; } ),
    '2^n'    => calc( function( $n ) { return pow( 2, $n ); } ),
    'n!'     => calc( function( $n ) { return fact( $n ); } ),
  ];
  print_result( $spec, $data );
}

function lg( $n ) { return log( $n, 2 ); }

function fact( $n ) {
  $result = 1;
  for ( $i = $n; $i >= 1; $i-- ) {
    $result *= $i;
  }
  return $result;
}

function calc( $fn ) {
  global $spec;
  $n = 1;
  $result = [];
  foreach ( $spec as $label => $bound ) {
    $result[ $label ] = exhaust( $fn, $n, $bound );
  }
  return $result;
}

function exhaust( $fn, &$n, $bound ) {
  while ( get_time( $fn, $n ) < $bound ) { $n *= 2; }
  // 2022-12-12 jj5 - just return the point between the value which fits and the value which doesn't
  return ( $n + ( $n / 2.0 ) ) / 2.0;
}

function get_time( $fn, $n ) {
  return $fn( $n ) * MICROSECOND;
}

function print_result( $spec, $data ) {
?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
  <title>Comparison of running times</title>
  <meta charset="utf-8">
  <meta name="date" content="Mon 12 Dec 2022 04:54:20 AEDT">
  <meta name="author" content="John Elliot V">
  <meta name="viewport" content="width=device-width,initial-scale=1">
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
  <link href="/favicon.ico" rel="icon">
  <link
    rel="stylesheet"
    type="text/css"
    href="https://www.staticmagic.net/global/default.css?v=2022-12-12-045420">
  <script src="https://www.staticmagic.net/global/default.js?v=2022-12-12-045420"></script>
<style>
html {
  min-height: 101%;
  margin: 1rem;
  padding: 0px;
}
.label {
  min-width: 3rem;
  text-align: center;
}
td {
  text-align: right;
}
thead tr td {
  background-color: #fff !important;
}
</style>
</head>
<body>
  <main>
    <h1>Comparison of running times</h1>
    <p>Taken from page 15 of
      <a href="https://smile.amazon.com/dp/0262033844">Introduction to Algorithms 3ed</a>, for
      each function <i>f(n)</i> and time <i>t</i> in the following table, we determine the
      largest size <i>n</i> of a problem that can be solved in time <i>t</i>, assuming the
      algorithm to solve the problem takes <i>f(n)</i> microseconds.</p>
<?php

  print_table( $spec, $data );

?>
    <p>The above table generated with the following code:</p>
    <pre>
<?php

  echo htmlspecialchars( file_get_contents( __FILE__ ) );

?>
    </pre>
  </main>
</body>
</html>
<?php
}

function print_table( $spec, $data ) {
  echo "<table class='nice-table'>\n";
  echo "<thead>\n";
  echo "<tr>\n";
  echo "<td class='label'></td>\n";
  foreach ( $spec as $column => $bound ) {
    echo "<th>1<br>$column</th>\n";
  }
  echo "</tr>\n";
  echo "</thead>\n";
  echo "<tbody>\n";
  foreach ( $data as $fn => $values ) {
    if ( $fn === "2^n" ) { $fn = "2<sup>n</sup>\n"; }
    echo "<tr>\n";
    echo "<td class='label'>$fn</td>\n";
    foreach ( $spec as $column => $bound ) {
      echo "<td>" . format( $values[ $column ] ) . "</td>\n";
    }
    echo "</tr>\n";
  }
  echo "</tbody>\n";
  echo "</table>\n";
}

function format( $value ) {
  $strval = strval( $value );
  if ( strpos( $strval, 'E+' ) > 0 ) { return $strval; }
  return number_format( $value );
}