# 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? – Sasho Nikolov May 28 '12 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. – Sasho Nikolov May 28 '12 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 '12 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 '12 at 5:19
• Because the part I'm really interested in is the inclusion of both f and t. – Owen May 28 '12 at 5:19

## 1 Answer

Analyzing algorithms on real word machines is complicated but there has been some work done in this area in terms of how an algorithm behaves based on access to memory hierarchy. External Memory or memory hierarchy access based analysis are much more useful in understanding how an algorithm grows for large data-sets and in modern machines on most problems external memory access is the one which creates most latency AFAIK. You should check out work done on Cache Oblivious algorithms and algorithms for External Memory for understanding the run time cost of your problem.

I am not aware of work done on CPU cycles but someone who knows about this can pitch in.

• Thats a good point. I think I was being a little unclear to say "CPU cycles". How about take it to mean "steps" and take the question from there. – Owen May 28 '12 at 3:36
• After thinking I am wondering should I change this answer to a comment to the question. Doesn't directly answer the question other than pointing a change in analysis. – Sai Venkat May 29 '12 at 2:47