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