This is my third installation of my "Reasoning on Efficiency" series. This question builds on my first question in the series: "Reasoning on Efficiency (1)"

The question in this installment builds on the ideas developed in the first question.

Advertising out of the way, let's proceed. My question is this:

Giving a particular problem $P_i$. Let the most optimum possible algorithm* for solving $P_i$ be $A_{ij}$,
$$A_{ij} \rightarrow H(x)$$

My question is this: Is it possible to prove that $$H(x) = \Theta\left(f(x)\right)$$
Where $f(x)$ is a function with known time complexity.

*If for any Problem $P_i$, $K_i$ is the set of all possible algorithms(both known and unknown) for solving $P_i$. A given algorithm $A_{ij} \in K_i$ is said to be the "most optimum possible" if: $$\forall A_{ix} \in K_i, A_{ij} = o\left(A_{ix}\right)$$

  • 1
    $\begingroup$ What is $i$? What is $j$? What does $A_{ij}=K(x)$ mean? What do you mean by "most optimum possible algorithm"? In particular, the linear speedup theorem says that, whenever you can find an algorithm with running time $f(x)$, I can give you an algorithm with running time $f(x)/c$ for any $c>0$. $\endgroup$ – David Richerby Dec 8 '16 at 11:37
  • 3
    $\begingroup$ Your questions are not that connected and since the first one was closed it is not a good source of explanations. The title you have chosen is not very meaningful one. Please explain by using edit, not in the comments or closed post. The question should be self-contained. $\endgroup$ – Evil Dec 8 '16 at 11:52
  • $\begingroup$ @DavidRicherby $i$ is the problem index. $j$ is the Algorithm index. $\endgroup$ – Tobi Alafin Dec 8 '16 at 12:18
  • 2
    $\begingroup$ @TobiAlafin Index in what? You've stated one problem and one algorithm. Why does the problem need one index and the algorithm two? Where I'm going with this is that the way you write mathematics suggests that you don't really understand the concepts that you're trying to discuss and extend. You really do need to understand the existing systems before you try to improve on them with a system of your own. D.W. suggested a lot of resources in his answer to your second question and I strongly recommend that you read those. If you need help understanding them, ask specific questions about them. $\endgroup$ – David Richerby Dec 8 '16 at 12:45
  • 2
    $\begingroup$ Also, note that you're consistently confusing algorithms and running times. It doesn't make sense to write "$A=f$", where $A$ is an algorithm and $f$ is a function measuring the performance of $A$. It's like writing "my car=50km/h". Your car does not equal 50km/h, because "equals" means "is exactly the same thing as" and a car cannot possibly be exactly the same thing as a speed. Note also that functions, in the mathematical sense, don't have complexities: functions measure complexity (in exactly the same way that a numbers don't have speed; they're used to measure speed). $\endgroup$ – David Richerby Dec 8 '16 at 12:47

The answer depends on your computation model. Let's consider the case of Turing machines, and the language $L$ over $\{0,1\}$ of words ending in $1$. This language has time complexity $n+1$.

Blum's speedup theorem states that optimal algorithms don't exist for all problems, in a very strong sense (which is explained in the Wikipedia article).

Finally, let me mention that your notion of optimality is too restrictive. Given an algorithm with running time $T(n)$ for any problem, it is easy to construct (in the Turing machine model) another algorithm whose running time is also $T(n)$. So no language can have an optimal algorithm in this very strong sense. Even if you consider only running times, it is easy to construct (in the same model) another algorithm with the different running time $T(n)+1$. So no non-trivial language can have an optimal running time in your very strong sense.


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