Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 $\max(a_1, a_2, \ldots, a_n)$? 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.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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