<p>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.</p>

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

CC BY-SA 3.0
2012-05-28T03:36:39.933Z
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
CC BY-SA 3.0
2012-05-29T02:47:34.833Z
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
CC BY-SA 3.0
2012-05-28T02:49:19.780Z
2012-05-28T02:49:19.780Z
Sai Venkat
<p>Fix $f(\_; \_)$, which represents a class of optimization problems, ie, for a specific $P$, $f(\_; P)$ is a function we'd like to optimize.</p>

<p>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.</p>

<p><strong>edit (much cut)</strong>: 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 <a href="http://theory.stanford.edu/~tim/f11/l1.pdf" rel="nofollow">notes Sasho linked to</a>.</p>

<p>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.</p>

<p>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</p>

<blockquote>
  <p>$\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'\}$</p>
</blockquote>

<p>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)$.</p>

<p>Maybe that will work, not sure. Let me give an example.</p>

<p><strong>Example:</strong> 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$).</p>

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

<pre><code>If a &gt; b:
    Search through the list 1 by 1 looking for the number 1,
    then output that index.
Else:
    Output 1.
</code></pre>

<p>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.</p>

<p><strong>Question:</strong> Does this problem, of including <em>both</em> an algorithm's <em>own</em> 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?</p>

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

CC BY-SA 3.0
2012-05-28T04:56:26.980Z
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
CC BY-SA 3.0
2012-05-28T05:01:21.500Z
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 http://theory.stanford.edu/~tim/f11/l1.pdf. I suggest first constraining your computation model.
Sasho Nikolov
CC BY-SA 3.0
2012-05-28T05:10:56.260Z
@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
CC BY-SA 3.0
2012-05-28T05:19:17.327Z
@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
CC BY-SA 3.0
2012-05-28T05:19:28.903Z
Because the part I'm really interested in is the inclusion of *both* f and t.
Owen
CC BY-SA 3.0
2012-05-28T05:19:30.400Z
I see, sorry for misreading your notation. Maybe you are not asking for instance optimality after all
Sasho Nikolov
CC BY-SA 3.0
2012-05-28T05:34:27.900Z
Actually, after looking at that link, no, you're right, I'm not :) I'm talking about something intentionally weaker because I'm not optimistic about instance optimality ever happening.
Owen
CC BY-SA 3.0
2012-06-10T18:43:15.720Z
This is a fun question, but I would suggest severely restricting it by changing the computational model as @SashoNikolov suggests. One way to do this is to limit your optimization problems to linear ones and your algorithms to simplex algorithms. Then you have a clear way to measure the number of steps, and are in a domain where you can at least get your hands on some handles without making the problem trivial.
Artem Kaznatcheev
<ds.algorithms><optimization>
Is it possible to include an optimization algorithm's own running time in the cost?
Owen
# Is it possible to include an optimization algorithm's own running time in the cost?

(Asked by: username_0 on 2012-05-27)

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

**Tags:** ds.algorithms, optimization

> **Comments:**
> **username_1**: 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?  
> **username_1**: 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 http://theory.stanford.edu/~tim/f11/l1.pdf. I suggest first constraining your computation model.  
> **username_0**: @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.  
> **username_0**: @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? :)  
> **username_0**: Because the part I'm really interested in is the inclusion of *both* f and t.  
> **username_1**: I see, sorry for misreading your notation. Maybe you are not asking for instance optimality after all  
> **username_0**: Actually, after looking at that link, no, you're right, I'm not :) I'm talking about something intentionally weaker because I'm not optimistic about instance optimality ever happening.  
> **username_2**: This is a fun question, but I would suggest severely restricting it by changing the computational model as @SashoNikolov suggests. One way to do this is to limit your optimization problems to linear ones and your algorithms to simplex algorithms. Then you have a clear way to measure the number of steps, and are in a domain where you can at least get your hands on some handles without making the problem trivial.  

---

## 1 answers

### Answer by username_3 on 2012-05-28. Score: 1

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.

> **Comments:**
> **username_0**: 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.  
> **username_3**: 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.  

---

