# Is it possible to include an optimization algorithm's own running time in the cost?

Fix $f(\_; \_)$, which represents a class of optimization problems, ie, for a specific $P$, $f(\_; P)$ is a function we'd like to optimize.

Now, we have an algorithm $A$ that takes as input $P, a, b$, runs for $t$ CPU cycles, and outputs $x$ such that $a{\cdot}f(x; P) + b{\cdot}t$ is minimized.

edit (much cut): As Sasho points out, it is very tricky to define in what sense $A$ "minimizes" $a{\cdot}f(x; P) + b{\cdot}t$. I'm pretty convinced now that the criterion I gave earlier (see older version of this question) is no good. Let me try a different one similar to the one from the notes Sasho linked to.

Let $\mathcal{A}$ be the set of algorithms that take in $a, b, P$ and give out some $x$. Also say that the $P$s have "sizes" which are integers.

Say then that $A$ is optimal iff for every $A' \in \mathcal{A}$ and $a, b \in R$ there exists an $N \in Z$ such that

$\forall{n} \ge N, ~~ \operatorname*{max}_{P \text{ with size ≤ n }}\{a{\cdot}f(x_P; P) + b{\cdot}t\} \leq \operatorname*{max}_{P \text{ with size ≤ n }}\{a{\cdot}f(x'_P; P) + b{\cdot}t'\}$

where $x, t$ are the result and running time of $A(a,b,P)$ and $x', t'$ are the result and running time of $A'(a,b,P)$.

Maybe that will work, not sure. Let me give an example.

Example: Say we take the problem of finding the smallest element in a list. Say we are given a list of size $n$, which we know contains some permutation of $1 ... n$, and we are asked to give an index at which lies a value that is as small as possible (ie, if the list were $[2, 1, 3]$ the best we could output would be $2$, then $1$, then $3$).

Say accessing the list (random access) takes $1$ step, everything else takes $0$ steps. Now our algorithm ($A$) will be:

If a > b:
Search through the list 1 by 1 looking for the number 1,
then output that index.
Else:
Output 1.


For a list of size $\leq n$, the worst this can do is $min(a + b{\cdot}(n-1), a{\cdot}n)$ (note that the comparison, somewhat unrealistically, takes no time). Any algorithm guaranteed of finding a value no less than $k$ must see at least $n - k$ elements of the list, giving a worst-case score of $a{\cdot}k + b{\cdot}(n - k)$. Differentiate that wrt $k$ gives $a - b$, and substituting $1$ or $n$ for $k$ gives $a + b{\cdot}(n-1)$ or $a{\cdot}n$ respectively, so by induction $A$ scores at least as well. So, according to the above optimality constraint, $A$ is optimal.

Question: Does this problem, of including both an algorithm's own running time, and the result of another problem, in its score, have a name? Or does something similar have a name? Can such an algorithm usually exist in theory? Any other information I could check out?

(This question was inspired by a friend of mine who's computer freezes up for several minutes when he runs optimization algorithms).

• This is an interesting question! However, getting the definitions right is non-trivial. How do you define "all but finitely many"? You need some encoding of turing machines/RAM machines/etc., and you need to make sure that there are always a finite number of ways to encode "check if input is $x$ and output optimal answer". on the other hand, how do you know that it's not the case that all but a finite number of algorithms perform horribly on any given input? May 28, 2012 at 4:56
• in essence, if we ignore optimizing $f$ and just focus on running time, you are asking for an algorithm that outperforms any other algorithms on an instance per instance basis. this is known as instance optimality, and, as you observed, is hard to get because it's so easy to define cheating algorithms. but there are interesting results, see theory.stanford.edu/~tim/f11/l1.pdf. I suggest first constraining your computation model. May 28, 2012 at 5:01
• @SashoNikolov for "finitely many", that just applies to P, not to algorithms, which is some parameter that we can hope is easy to count. But youre right that migh not be the right way to knock out cheating algorithms. I'll check out your link.
– Owen
May 28, 2012 at 5:10
• @SashoNikolov so maybe a better way to phrase the question would be, assuming we've already defined a good way to define instance per instance optimality, can there be such an A? :)
– Owen
May 28, 2012 at 5:19
• Because the part I'm really interested in is the inclusion of both f and t.
– Owen
May 28, 2012 at 5:19