2
$\begingroup$

Let $O(f(n))$ be the minimum time complexity for output a real sequence $\{a_i\}$.

The input of the algorithm is a integer $n$. It output the finite sequence $a_1, a_2, \ldots, a_n$. (Clearly $f(n)\geq n$.)

What can we say about the time complexity of

\begin{equation*} \max(a_1, a_2, \ldots, a_n)? \end{equation*}

Is there always an algorithm to solve this problem in time complexity less than $O(f(n))$?

For example, the algorithm that output the sequence of natural numbers is a $O(n)$ algorithm. Finding the maximum value between 1 and n is $O(1)$.

If we have some more information, like Kolmogorov complexity of the sequence, how will it change the time bounds?

It seems that if a sequence can be described easily, we can find a way to find the maximum value easier than naively compute the sequence and compare.

2 Answers 2

3

Let $a_n = $ number of 1's in the first $n$ terms of another given 0-1 sequence, $b_n$.

For example, $a_n$ could equal the number of odd perfect numbers between 1 and (2n-1), or the number of Fermat primes $2^{2^k} + 1$ with $k \leq n$, or the number of the first $n$ LISP programs that terminate within 4000*(program-length)^4 steps.

$a_n$ is non-decreasing, but to find $a_n$ (which is the maximum of the first $n$ terms) is as difficult as calculating all the previous $a_i$.

1

Not exactly what you're looking for, but probably related: global optimization of one-variable real functions is NP-complete.