1
$\begingroup$

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.

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

2 Answers 2

0
$\begingroup$

Allowed probably isn't the right word. You can do anything you want.

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.

Perhaps what would help you would be to learn about models of computation: Turing machines, RAM model, transdichotomous model. Many algorithm textbooks start with a discussion of how running time is computed (which is implicitly a model of computation), which would be a good place to start.

$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – Qwerty Boy
    Commented Jul 20, 2022 at 16:10
  • $\begingroup$ @QwertyBoy, sorry, I can't understand what you're asking. Please don't use the comments to ask new questions or revise your question. It's important to be clear about what you are asking when you post the question. Perhaps you can post a new question that states your question more clearly. $\endgroup$
    – D.W.
    Commented Jul 20, 2022 at 16:27
0
$\begingroup$

The computational model is implicit in the question: the basic operation is the $=k \,?$ query, and taken as the unit. Whatever any actual implementation.

In fact, you don't evaluate a time-complexity, but a query-complexity. Just like when you rate a sorting algorithm based solely on the number of comparisons.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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