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.


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$.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.