Time intricacy to locate the extremal value of a function

Allow $O(f(n))$ be the minimum time intricacy for result an actual series $\{a_i\}$.

The input of the algorithm is a integer $n$. It result the limited series $a_1, a_2, \ldots, a_n$. (Plainly $f(n)\geq n$.)

What can we claim concerning the moment intricacy of

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

Exists constantly an algorithm to address this trouble in time intricacy much less than $O(f(n))$?

As an example, the algorithm that result the series of all-natural numbers is a $O(n)$ algorithm. Locating the maximum value in between 1 and also n is $O(1)$.

If we have some even more details, like Kolmogorov intricacy of the series, just how will it transform the moment bounds?

It appears that if a series can be defined conveniently, we can locate a means to locate the maximum value less complicated than naively calculate the series and also contrast.

2019-05-05 11:14:12
Source Share
Answers: 2

Not specifically what you're seeking, yet possibly relevant : international optimization of one - variable actual features is NP - full.

2019-05-08 08:42:46

Let $a_n = $ variety of 1's in the first $n$ regards to an additional offered 0 - 1 series, $b_n$.

As an example, $a_n$ can amount to the variety of weird excellent numbers in between 1 and also (2n - 1), or the variety of Fermat tops $2^{2^k} + 1$ with $k \leq n$, or the variety of the first $n$ LISP programs that end within 4000 * (program - size) ^ 4 actions.

$a_n$ is non - lowering, yet to find $a_n$ (which is the maximum of the first $n$ terms) is as hard as computing all the previous $a_i$.

2019-05-08 08:38:41