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.