Say I have some problem of $O\left(n^k\right)$ complexity.

If I were to solve the problem on a computer $x$, it would take time $t$.

Now I have a new computer $x'$, which has double the computing power of $x$.

How long would it take $x'$ to solve the same problem in terms of $t$?

  • $\begingroup$ What is your definition of polynomial time, $n$, $k$, etc.? One definition is the number of tape head movements for a single-tape, deterministic Turing Machine (which is one definition of the class $\mathcal{P}$). $\endgroup$ – Ryan Mar 19 '15 at 1:12
  • $\begingroup$ @Ryan I did not realise there were multiple definitions of polynomial time. I would assume it's the one defined for class P. Thanks. $\endgroup$ – JibbyJames Mar 19 '15 at 1:16
  • $\begingroup$ @Ryan A polynomial number of operations of machine $x$. It doesn't really matter what those operations are, assuming that $x'$ has the same basic operations and does them twice as fast. $\endgroup$ – David Richerby Mar 19 '15 at 1:17
  • 2
    $\begingroup$ You want to use $\Theta$. With only $O$ you know nothing. Note furthermore that "computing power" as one dimensional parameter is not a real thing. (For example, if your CPU is twice as fast but memory is slower, most algorithms will not experience a speed-up by factor two, if any.) $\endgroup$ – Raphael Mar 19 '15 at 7:02
  • 2
    $\begingroup$ Imho it doesn't really matter what the complexity of the problem is. If a computer takes time t, another computer that's twice as fast takes time 0.5t. Isn't that obvious? $\endgroup$ – Albert Hendriks Mar 19 '15 at 13:33

It will take half the time of course, $t'=t/2$, and the asymptotic complexity remains $O(n^k)$ !

  • $\begingroup$ I guess that the OP was expecting an answer like $t/\sqrt[k]2$, indeed irrelevant. $\endgroup$ – Yves Daoust Mar 20 '15 at 13:21
  • $\begingroup$ I think I should have asked what Yuval edited my question to be. $\endgroup$ – JibbyJames Mar 20 '15 at 13:56
  • $\begingroup$ I guess the question should rather have been: "if the computing power doubles, how many elements can be processed in the same time", the (empirical) answer being $\sqrt[k]2n$. $\endgroup$ – Yves Daoust Mar 20 '15 at 14:00
  • $\begingroup$ That is actually a far better formula for explaining what I am writing about. Thank you. $\endgroup$ – JibbyJames Mar 20 '15 at 14:27

Comment: This actually answers a much more interesting question:

Suppose algorithm $A$ runs in time $O(n^k)$ on inputs of length $n$. If we double the input length, how long would it take $A$ to run on the new input in terms of its running time on the original output?

The answer you were supposed to give is:

$2^kT$, where $k$ is the exponent in the running time $O(n^k)$.

The idea is that if your running time is exactly $T(n) = Cn^k$ then $$ T(2n) = C(2n)^k = 2^k(Cn^k) = 2^kT(n). $$

However, the running time need not be exactly $Cn^k$, and if it isn't, you can't really tell what the exact relation is between $T(2n)$ and $T(n)$. You can come up with pathological examples like $$ T(n) = \begin{cases} 1 & \text{if $n$ is odd}, \\ n & \text{if $n$ is even}. \end{cases} $$ If $n$ is odd then $T(2n) = 2nT(n)$, and the factor $2n$ isn't bounded; yet $T(n) = O(n)$ has polynomial growth.

If $T(n) = \Theta(n^k)$ then we can say that $T(2n) = \Theta(T(n))$, but it could still be that, say, $T(2n) < T(n)$, as in this examples: $$ T(n) = \begin{cases} 100n & \text{if $n$ is odd}, \\ n & \text{if $n$ is even}. \end{cases} $$ If $n$ is odd then $T(2n) = T(n)/50$.

  • $\begingroup$ I don't see why we increase instance sizes; if we solve the same problem at twice the speed, it takes us half as long. Granted, that's a really boring question, but I actually don't see how the original question is related to complexity. $\endgroup$ – G. Bach Mar 20 '15 at 1:02
  • $\begingroup$ @G.Bach I might have misread the question. Usually these questions ask for what my answer refers to. Otherwise, as you say, the nature of the original running time doesn't come into play at all. $\endgroup$ – Yuval Filmus Mar 20 '15 at 1:04
  • 2
    $\begingroup$ I think what we have in mind is the question, "given twice the processing power, how much larger are the instances I can solve in fixed time $T$?". The question as stated seems to be trivial indeed. $\endgroup$ – Raphael Mar 20 '15 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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