# Relation between algorithms and models

I have found this question some time ago. While reading it, I had a problem with understanding the following idea:

Question, part 1: Is one allowed to talk about the time/space bound of any algorithm (e.g. the $$O(n)$$ time bounded algorithm proposed in the cited question's comments) without considering at least one concrete model (e.g. a Turing machine) that could guarantee a solution to the problem within that bound?

That is to say, would an algorithm $$A$$ presenting some worst-case time upper-bound $$O(f(n))$$ always be guaranteed to have one corresponding Turing machine $$M$$ that could run it on all inputs within the same given time bound?

Question, part 2: How could the algorithm for the cited problem be represented on one Turing machine? Does the fact that Alice owns information Bob does not (the number $$k$$) influence the way the Turing machine would be built? How do you see it?

Thank you very much.

• Please ask only one question per post. If you have multiple questions, each one can be posted separately. Thank you.
– D.W.
Jul 20 at 16:03

You can certainly have a lower bound without being sure whether it is tight or not. For instance, I can say that sorting takes at least $$\Omega(n)$$ time, without knowing whether there is an algorithm for sorting that runs in $$O(n)$$ time.
• This is true, but what I am especially interested in is whether one can declare that the cited problem may be resolved in $O(n)$ if they cannot design a Turing machine to run in $O(n)$ for all inputs. What do you think? Can such a Turing machine be designed? How would it take all that inputs ($n$, $k$, $a_i$) in the first place and manage to preserve $k$ private? Jul 20 at 16:10