[31] Show that there there is an algorithm FASTSEARCH that does the following: Let A : X → Y be a given algorithm or specification.

Let B be an algorithm, computing provably the same function as A with computation time provably upper bounded by the function tB(x). Let time tB(x) be the time needed to compute the time bound tB(x). Then the algorithm FASTSEARCH computes A(x) in time at most 5tB(x) +

dBtime tB(x)+cB, with constants dB and cB depending on B but not on x. Neither B, tB, nor the mentioned proofs need to be known in advance for the construction of FASTSEARCH.

Comment. The algorithm FASTSEARCH is an optimized version of SEARCH, where the proportionality constant of 2K(k)+O(1) of the latter is replaced by just 5, but at the cost of truly gigantic additive terms depending on k but not on x. By the reasoning in Example 7.5.2, there is a fixed constant c such that the trivial SIMPLE algorithm simulates every inversion problem running in t(n) steps in at most c · t(n) steps ignoring additive terms depending on the inversion problem but not on the input. Source: [M. Hutter, Int. J. Found. Comput. Sci., 13:3 (2002), 431–443].